首页 > 代码库 > TYVJ1264

TYVJ1264

2024-07-19 11:35:03   220人阅读

水题
裸数字三角形，稍微升级
从下游往上推
设dp[i][j]表示到达(i,j)时所能得到的最大分数
目标dp[1][j]中的最大值
方程:
dp[i][j] = a[i][j]+max(dp[i+1][j-1],dp[i+1][j],dp[i+1]
[j+1])
特殊情况加特判即可

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6  7 const int maxn = 8001; 8 const int maxm = 1001; 9 int a[maxn][maxm];10 int main()11 {12     freopen("in.txt","r",stdin);13     int n,m;14     cin>>m>>n;15     for(int i = 1;i<=n;++i)16         for(int j = 1;j<=m;++j)17             scanf("%d",&a[i][j]);18     for(int i =  n-1;i>=1;--i)19         for(int j = 1;j<=m;++j)if(a[i][j]!=-1)20         {21             if(j==1)a[i][j]+=max(a[i+1][j],a[i+1][j+1]);22             else if(j==m)a[i][j]+=max(a[i+1][j],a[i+1][j-1]);23             else a[i][j]+=max(a[i+1][j],max(a[i+1][j-1],a[i+1][j+1]));24         }25     int ans = -1;26     for(int i = 1;i<=m;++i)27         ans=max(ans,a[1][i]);28     printf("%d\n",ans);29 30     return 0;31 }

 

TYVJ1264


联系
我们