P1004方格取数

这是提高组得一道动态规划题，也是学习y氏思考法的第一道题。

题意为给定一个矩阵，里面存有一些数，你从左上角开始走到右下角，另一个人从右下角开始走到左上角，使得两个人取数之和最大，当然一个数只可以取走一次并且行走规则与采花生一样。开始之前我们把问题进行一下转化，把右下角的人拿到左上角来，也让其往下走。然后我们开始思考1.集合？从(1,1,1,1)到(i,j,i2,j2)的所有路线中的答案；2.属性？最大值 3.集合计算与划分？根据最后原则，除了左上角dp[i,j,i2,j2]是由上上，左左，左上，上左加上本身的数，四种状态转移过来的，以此得出状态转移方程。那么还有一点我们需要注意，就是我们不可以同时走两个点，所以当i1=i2时，我们只需要加上mp[i1][k-i1]的值就好4.优化？我们只需要保持步数一样，那么i1,i2,k就可以表示出j1,j2了（k-i1)。

代码

#include<bits/stdc++.h>

using namespace std;

int dp[][][];

int n,m;

int mp[][];

int main(){

    cin>>n;

    int a,b,c;

    memset(mp,,sizeof(mp));

    while(cin>>a>>b>>c){

        mp[a][b]=c;

    }

    for(int k=;k<=*n;k++){

        for(int i1=;i1<=n;i1++){

            for(int i2=;i2<=n;i2++){

                int j1=k-i1;

                int j2=k-i2;

                if(j1>=&&j2>=&&j2<=n&&j1<=n){

                    int t=mp[i1][j1];

                    if(i1!=i2) t+=mp[i2][j2];

                        dp[k][i1][i2]=max(dp[k-][i1-][i2-]+t,dp[k][i1][i2]);//dd

                        dp[k][i1][i2]=max(dp[k-][i1-][i2]+t,dp[k][i1][i2]);//dr

                        dp[k][i1][i2]=max(dp[k-][i1][i2-]+t,dp[k][i1][i2]);//rd

                        dp[k][i1][i2]=max(dp[k-][i1][i2]+t,dp[k][i1][i2]);//rr

                }

            }

        }

    }

    cout<<dp[*n][n][n];

    return ;

}

巴特西

P1004方格取数

最新文章

热门文章