POJ 1163解题报告-白红宇

POJ 1163解题报告

阅读量：4205 次

发布时间：2019-05-26

本文共 1002 字，大约阅读时间需要 3 分钟。

POJ 3176和这道题是同一道题。

这道题是道简单的动态规划题，从上往下扫描即可。arr[i][j] = max(arr[i - 1][j - 1], arr[i - 1][j]) + arr[i][j];

空间有节省的地方，就是输入的时候直接处理，不必等到整个存储完了再按行进行处理，因为当前行只与前面一行有关。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int arr[100][100];int main(){// FILE *fin, *fout;// fin = fopen("numtri.in", "r");// fout = fopen("numtri.out", "w");// assert(fin != NULL && fout != NULL); int r; fscanf(stdin, "%d", &r); //fscanf(fin, "%d", &r); //int cnt = 0; for(int i = 0; i < r; ++i) { for(int j = 0; j < i + 1; ++j) { //fscanf(fin, "%d", &arr[i][j]); fscanf(stdin, "%d", &arr[i][j]); } } for(int i = 1; i < r; ++i) { arr[i][0] = arr[i - 1][0] + arr[i][0]; for(int j = 1; j < i + 1; ++j) { arr[i][j] = max(arr[i - 1][j - 1], arr[i - 1][j]) + arr[i][j]; } } int max = 0; for(int i = 0; i < r; ++i) { if(arr[r - 1][i] > max) max = arr[r - 1][i]; } fprintf(stdout, "%d\n", max); //fprintf(fout, "%d\n", max); return 0;}