首页 > 代码库 > TYVJ1106

TYVJ1106

2024-07-19 06:55:34   220人阅读

巨坑。。。
和数字三角形原理差不多，就是状态多一点，而且前后状态有影响
坑1：在第i行，从第一个位置可以直接走到最后一个位置，说明没一层这是一个圆
坑2：第i行的第一个位置可以直接走到上面一行的最后一个位置，这尼玛还是一个圆锥啊。
设dp[i][j]表示到(i,j)时最小的分数,从下往上推
dp目标 dp[1][1]
(i,j)可以从左下、右下、左、右到达，从下往上还好说，这左右还可以走的话，不好办了。。
首先对于每一层，先由下面一层推上来，
一般情况dp[i][j]=a[i][j]+min(dp[i+1][j],dp[i+1][j+1])
特殊情况需特判(例如说山腰就是每一行开头和结尾的位置)

从下面推上来之后，遍历当前层，找到这一层的最小值，这个值可以确定就是dp[i][j]的值，然后再用这个点将这一层都更新一遍。从这个点向右推一圈(注意是一圈),向左推一圈，就可以把每个点都更新了，需要思考一下这个方法的正确性，但是不用怀疑，它确实是对的。

这破题从中午开始搞到下午三点，后来觉得没错了，交了几次，老是只有第七点，，后来拿了数据，怎么也过不了，当时那个烦呐，后来等到晚饭回来，看了一下，尼玛在一万个字母当中把几个i写成了n，改之，果断AC

 1 //8594   4187 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #define INF 11111111 7 using namespace std; 8 const int maxn = 1005; 9 int a[maxn][maxn],dp[maxn][maxn];10 int main()11 {12     //freopen("in.txt","r",stdin);13     int n;14     cin>>n;15     memset(dp,0,sizeof(dp));16     memset(a,0,sizeof(a));17     for(int i = 1;i<=n;++i)18         for(int j = 1;j<=i;++j)19             scanf("%d",&a[i][j]);20     for(int i = 0;i<=n+1;++i)21         for(int j = 0;j<=n+1;++j)22             dp[i][j] = INF;23     dp[n][0] = 0;24     for(int i = 1;i<=n;++i)25         dp[n][i]=dp[n][i-1]+a[n][i];26     for(int i = n;i>=2;--i)27         if(i==n)dp[n][i] = min(dp[n][i],dp[n][1]+a[n][i]);28         else dp[n][i] = min(dp[n][i],dp[n][i+1]+a[n][i+1]);29     for(int i = n-1;i>=1;--i)30     {31         //从下更新到上一层32         for(int j = 1;j<=i;++j)33             if(j==1)dp[i][j] = a[i][j]+min(dp[i+1][i+1],min(dp[i+1][j],dp[i+1][j+1]));34             else if(j==i) dp[i][j]=a[i][j]+min(dp[i+1][1],min(dp[i+1][j],dp[i+1][j+1]));35             else dp[i][j] = a[i][j]+min(dp[i+1][j],dp[i+1][j+1]);36         //获取第i层最小dp的位置37         int mmin = INF,min_x;38         for(int j = 1;j<=i;++j)if(mmin>dp[i][j]){mmin = dp[i][j];min_x = j;}39         //从最小位置向右更新一圈40         for(int j = min_x+1;j<=i;++j)dp[i][j]=min(dp[i][j],dp[i][j-1]+a[i][j]);41         dp[i][1] = min(dp[i][1],dp[i][i]+a[i][1]);42         for(int j = 1;j<min_x;++j)dp[i][j] = min(dp[i][j],dp[i][j-1]+a[i][j]);43         //从最小位置向左更新一圈44         for(int j=min_x-1;j>=1;--j)dp[i][j]=min(dp[i][j],dp[i][j+1]+a[i][j]);45         dp[i][i] = min(dp[i][i],dp[i][1]+a[i][i]);46         for(int j=i;j>min_x;--j)dp[i][j]=min(dp[i][j],dp[i][j+1]+a[i][j]);47 48     }49 50      printf("%d\n",dp[1][1]);51     return 0;52 }

 

TYVJ1106


联系
我们