???DP(动态规划)怎么本地测试对,洛谷提交就错?

P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

Eric12 @ 2021-11-12 21:59:37

思路:把这个三角形看成直角三角形,只能向下或右下走。

然后用“正方形存储方式”存储直角三角形进行DP。

大佬看看,哪里错了?

//如果把题目中看成直角三角形的话,可以向下或向右走。
//思想:等腰三角形--三角形--正方形 
#include <iostream>
#include <cstdio> 
using namespace std;
int r,a[1001][1001],x,y,f[1001][1001],nowmax=-9999999,nowx=1,nowy=1;
char c;
int main()
{
    cin>>r;
    c=getchar();//第一个数输入完后,会有换行\n输入。 
    while(nowx<=r)
    {
        c=getchar();
        if(c!=' '&&c!='\n')
        {
            a[nowx][nowy]=c-'0';
            nowy++;
        }
        else if(c=='\n')
        {
            nowx++;
            nowy=1;
        }
    }
    f[1][1]=a[1][1];
    for(int i=2;i<=r;i++)
        f[i][1]=f[i-1][1]+a[i][1];
    for(int i=2;i<=r;i++)//行 
        for(int j=2;j<=r;j++)//列 
        {
            f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
            nowmax=max(nowmax,f[i][j]);
        }
    cout<<nowmax<<endl;
    return 0;
}

by Eric12 @ 2021-11-12 22:02:41

还有,f是DP数组,表示(1,1)点到(下标1,下标2)的最大路径总数。


|