hdu2854 Beans 二維dp

二維動態規劃，先求每一行的最大和，組成新的一行，最後在求這一行的最大和
 
[cpp] 
#include<iostream> 
using namespace std; 
const int INF=200010; 
int Row[INF][2],Col[INF][2]; 
main() 
{ 
    int i,j,R,C,temp; 
    while(scanf("%d%d",&R,&C)!=EOF) 
    { 
        memset(Col,0,sizeof(Col)); 
        for(i=1;i<=R;i++) www.2cto.com
        { 
            memset(Col,0,sizeof(0)); 
            for(j=1;j<=C;j++) 
            { 
                scanf("%d",&temp); 
                Row[j][0]=max(Row[j-1][1],Row[j-1][0]); 
                Row[j][1]=Row[j-1][0]+temp; 
            } 
            Col[i][1]=Col[i-1][0]+max(Row[j-1][1],Row[j-1][0]); 
            Col[i][0]=max(Col[i-1][1],Col[i-1][0]); 
        } 
        printf("%d\n",max(Col[i-1][1],Col[i-1][0])); 
    } 
} 
作者：Time flies