posts - 403, comments - 310, trackbacks - 0, articles - 7
          
	
 
BlogJava ::
首頁 ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理


          
		          		
	
          
	
          
		
			
          
			
          
		          		
		
			
          
				
					
	
          
		
          
			
          
				USACO 1.1.5 Number Triangles
			
          
 			Posted on 2007-06-01 21:51 ZelluX 閱讀(267) 評論(0)  編輯  收藏  所屬分類: Algorithm 
			
			


		
          
		
          最簡單的DP，于是只用了一維數(shù)組稍微提高下難度，不過還是一次編譯一次提交成功了，恩

          

          /*
          PROG: numtri
          ID: 06301031
          LANG: C++
          */

          #include           <iostream>
          #include           <fstream>

          using namespace std;

          int main() {
              ifstream fin(          "numtri.in");
              ofstream fout(          "numtri.out");
                        int n;
              fin           >> n;
                        int i, j;
                        int f[1001];
                        for (i = 0; i <= n; i++) {
                  f[i]           = 0;
              }
                        for (i = 0; i < n; i++) {
                            for (j = 0; j <= i; j++) {
                                int x;
                      fin           >> x;
                      f[j]           += x;
                  }
                            int temp[1001];
                            for (j = 0; j <= i; j++) {
                      temp[j]           = f[j];
                  }
                  temp[i           + 1] = f[i];
                            for (j = 0; j <= i; j++) {
                                if (f[j] > temp[j + 1]) {
                          temp[j           + 1] = f[j];
                      }
                  }
                            for (j = 0; j <= i + 1; j++) {
                      f[j]           = temp[j];
                  }
              }

                        int max = 0;
                        for (i = 0; i <= n; i++) {
                            if (f[i] > max) {
                      max           = f[i];
                  }
              }
              fout           << max << endl;
                        return 0;
          }
          

          
	
          
	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          



    







          
        
	




主站蜘蛛池模板：
牙克石市|
宿迁市|
图木舒克市|
阿克苏市|
民权县|
湾仔区|
疏勒县|
铜鼓县|
托里县|
伊金霍洛旗|
镇康县|
宁陵县|
绵阳市|
剑阁县|
资源县|
馆陶县|
武义县|
大安市|
青龙|
巫山县|
乐山市|
莱阳市|
灌云县|
湾仔区|
宣城市|
福鼎市|
武乡县|
灵山县|
东城区|
武陟县|
五大连池市|
腾冲县|
阜城县|
孟津县|
城固县|
柞水县|
彰化县|
镶黄旗|
沛县|
铜山县|
拜泉县|