这题是一道很好的DP入门练手题
但是总有一些同学想到了贪心
所以让我来展示一下33分的贪心
1 #include <bits/stdc++.h> 2 #define fp(i,l,r) for(register int i=(l);i<=(r);i++) 3 #define fd(i,r,l) for(register int i=(r);i>=(l);i--) 4 using namespace std; 5 int _ans=0; 6 int n; 7 int a[1000][1000]; 8 int _count=0; 9 inline int _max(int a,int b){ 10 if(a>b){ 11 return a; 12 } 13 return b; 14 } 15 int yh13(int x,int y){ 16 if(x==n){ 17 return 0; 18 } 19 _ans+=_max(a[x+1][y],a[x+1][y+1]); 20 if(_max(a[x+1][y],a[x+1][y+1])==a[x+1][y]){ 21 yh13(x+1,y); 22 } 23 else{ 24 yh13(x+1,y+1); 25 } 26 } 27 int main(){ 28 scanf("%d",&n); 29 fp(i,1,n){ 30 fp(j,1,i){ 31 scanf("%d",&a[i][j]); 32 } 33 } 34 _ans=a[1][1]; 35 yh13(1,1); 36 printf("%d",_ans); 37 return 0; 38 } 39 //代码贼丑别吐槽
为什么会得33分呢？
让我们来分析一下
我们题目中的数据是这样的
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
按照的贪心的路径就应该是(1,1)->(2,2)->(3,2)->(4,2)->(5,2) 答案是28
没毛病，对不对？
错！
如果我们仔细观察，就会发现有(1,1)->(2,1)->(3,1)->(4,2)->(5,2)得到答案30
这是怎么回事呢？
这证明贪心是不可行的，因为这道题不具备贪心选择性质
听说搜索特别万能？那我试试看
1 #include <bits/stdc++.h> 2 #define fp(i,l,r) for(register int i=(l);i<=(r);i++) 3 #define fd(i,r,l) for(register int i=(r);i>=(l);i--) 4 using namespace std; 5 int _ans=0; 6 int n; 7 int a[1000][1000]; 8 int _count=0; 9 inline int _max(int a,int b){ 10 if(a>b){ 11 return a; 12 } 13 return b; 14 } 15 inline int search(int x,int y){ 16 _count+=a[x][y]; 17 if(x==n){ 18 _ans=_max(_ans,_count); 19 } 20 else{ 21 search(x+1,y); 22 search(x+1,y+1); 23 } 24 _count-=a[x][y]; 25 } 26 int main(){ 27 scanf("%d",&n); 28 fp(i,1,n){ 29 fp(j,1,i){ 30 scanf("%d",&a[i][j]); 31 } 32 } 33 search(1,1); 34 printf("%d",_ans); 35 return 0; 36 }//更丑了
从33分变成了55分 RE了
想必问题已经很明显了吧，这个程序搜索了重复的数字，所以我们可以据此加一个记忆化
1 #include <bits/stdc++.h> 2 #define fp(i,l,r) for(register int i=(l);i<=(r);i++) 3 #define fd(i,r,l) for(register int i=(r);i>=(l);i--) 4 using namespace std; 5 int n; 6 int a[1000][1000]; 7 int f[1000][1000]; 8 int _count=0; 9 inline int _max(int a,int b){ 10 if(a>b){ 11 return a; 12 } 13 return b; 14 } 15 inline int search(int x,int y){ 16 int _ans=0; 17 if(x==n){ 18 return a[x][y]; 19 } 20 if(f[x+1][y]==-1){ 21 f[x+1][y]=search(x+1,y); 22 } 23 if(f[x+1][y+1]==-1){ 24 f[x+1][y+1]=search(x+1,y+1); 25 } 26 _ans=_max(f[x+1][y],f[x+1][y+1])+a[x][y]; 27 return _ans; 28 } 29 int main(){ 30 scanf("%d",&n); 31 fp(i,1,n){ 32 fp(j,1,i){ 33 scanf("%d",&a[i][j]); 34 f[i][j]=-1; 35 } 36 } 37 printf("%d",search(1,1)); 38 return 0; 39 }//啊啊啊啊啊啊啊
这回没毛病了100分
时间复杂度从搜索的O(2^n)变成了O(n^2)
其实还有一个和搜索差不多的做法（这个在luogu博客我没有发上去了），用分治。
设定两个变量用以递归求得最优子结构，时间复杂度O(2^n)
1 #include <bits/stdc++.h> 2 #define fp(i,l,r) for(register int i=(l);i<=(r);i++) 3 #define fd(i,r,l) for(register int i=(r);i>=(l);i--) 4 using namespace std; 5 int ans=0; 6 int n; 7 int a[1000][1000]; 8 inline int _max(int a,int b){ 9 if(a>b){ 10 return a; 11 } 12 return b; 13 } 14 inline int fz(int x,int y){ 15 if(x==n){ 16 return a[x][y]; 17 } 18 int s1=fz(x+1,y); 19 int s2=fz(x+1,y+1); 20 return _max(s1,s2)+a[x][y]; 21 } 22 int main(){ 23 scanf("%d",&n); 24 fp(i,1,n){ 25 fp(j,1,i){ 26 scanf("%d",&a[i][j]); 27 } 28 } 29 printf("%d",fz(1,1)); 30 return 0; 31 }//这个是最丑的
可是你再看看这篇题解的第一句话这题是一道很好的DP入门练手题
有没有感觉被欺骗了？
我还是把DP的思路及代码交上来吧
这题从上往下推就需要有其他的判断了
所以我选择了从下往上**递推**
这样就符合了最优子结构性质了
状态转移方程 f[x][y]=max(f[x+1][y],f[x+1][y+1])+a[x][y];(其实不用多讲把)
最后献上代码
1 #include <bits/stdc++.h> 2 #define fp(i,l,r) for(register int i=(l);i<=(r);i++) 3 #define fd(i,r,l) for(register int i=(r);i>=(l);i--) 4 using namespace std; 5 inline int _max(int a,int b){ 6 if(a>b){ 7 return a; 8 } 9 else{ 10 return b; 11 } 12 } 13 int a[1000][1000],f[1000][1000]; 14 int main(){ 15 int n; 16 scanf("%d",&n); 17 fp(i,1,n){ 18 fp(j,1,i){ 19 scanf("%d",&a[i][j]); 20 f[i][j]=a[i][j]; 21 } 22 } 23 fd(i,n-1,1){ 24 fp(j,1,i){ 25 f[i][j]=_max(f[i+1][j],f[i+1][j+1])+a[i][j]; 26 } 27 } 28 printf("%d",f[1][1]); 29 return 0; 30 }//...
完美收场
That's all.