这样子是错的
有反例
百度“传纸条”
by tonylzq1 @ 2017-07-17 21:33:24
```cpp
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int a[10][10]={0},f[10][10]={0},ans,memo1[10][10],memo2[10][10],n,x,y,z;
cin>>n;
cin>>x>>y>>z;
a[x][y]=z;
while((x!=0)||(y!=0)||(z!=0))
{
cin>>x>>y>>z;
a[x][y]=z;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(f[i][j-1]>f[i-1][j])
{
f[i][j]=a[i][j]+f[i][j-1];
memo1[i][j]=i;
memo2[i][j]=j-1;
}
else
{
f[i][j]=a[i][j]+f[i-1][j];
memo1[i][j]=i-1;
memo2[i][j]=j;
}
}
ans=f[n][n];
x=n;y=n;
while((x!=0)&&(y!=0))
{
a[x][y]=0;
z=x;
x=memo1[x][y];
y=memo2[z][y];
}
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=a[i][j]+max(f[i-1][j],f[i][j-1]);
cout<<f[n][n]+ans;
return 0;
}
me too
```
by qianfujia @ 2017-08-08 09:06:20
why
by qianfujia @ 2017-08-08 09:07:10