首页 > 代码库 > TYVJ1414

TYVJ1414

2024-07-19 06:50:00   215人阅读

多进程DP
现在才知道多进程的是有多么的恶心。。。
做过了1011传纸条，这题就没什么难度了，只要在传纸条上加上一维就行，最恶心的地方在于，这题没有限定走过的不能走，所以，对于每个状态有八个方向可以转移过来。。。。具体看代码吧

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 41; 7 int a[maxn][maxn],dp[maxn+maxn][maxn][maxn][maxn]; 8 int main() 9 {10     //freopen("in.txt","r",stdin);11     int n;12     while(cin>>n)13     {14         for(int i = 1;i<=n;++i)15             for(int j = 1;j<=n;++j)16                 scanf("%d",&a[i][j]);17         memset(dp,0,sizeof(dp));18         dp[2][1][1][1] = a[1][1];19         for(int r = 3;r<=n*2;++r)20             for(int i = 1;i<r;++i)21                 for(int j = 1;j<r;++j)22                     for(int k = 1;k<r;++k)23                     {24                         int t = max(dp[r-1][i][j][k],max(dp[r-1][i][j-1][k],max(dp[r-1][i][j-1][k-1],dp[r-1][i][j][k-1])));25                         t = max(t,max(dp[r-1][i-1][j][k],max(dp[r-1][i-1][j][k-1],max(dp[r-1][i-1][j-1][k-1],dp[r-1][i-1][j-1][k]))));26                         int t1 = a[i][r-i],t2 = a[j][r-j],t3 = a[k][r-k];27                         t+=a[i][r-i];a[i][r-i] = 0;28                         t+=a[j][r-j];a[j][r-j] = 0;29                         t+=a[k][r-k];a[k][r-k] = t3;30                         a[i][r-i] = t1;a[j][r-j] = t2;31                         dp[r][i][j][k] = t;32                     }33         printf("%d\n",dp[n+n][n][n][n]);34     }35 36     return 0;37 }

 

TYVJ1414


联系
我们