棋盘DP

主要是在棋盘上的DP,棋盘上每个点的转移状态基本上都是已知的

//https://www.luogu.com.cn/problem/P1004

//首先提供二维dp,二维dp的思路为ij表示i行j列时的可以取得最大值
//类似于贪心,先进行第一遍循环,取到最优,然后把第一遍取的数全变为0,再进行第二遍的取
//但是这种方法并不一定是全局的最优解

//0    0    2    3    0    0    0
//0    0    3    0    0    0    0
//0    0    3    0    0    0    0
//0    0    0    0    0    0    0
//0    0    0    0    4    0    0
//0    0    0    0    4    0    0
//0    0    0    0    4    0    0
//如图，走第一遍可得出终点时最大值为20，去掉已经走过的点后图如下：                        
//0    0    0    3    0    0    0
//0    0    0    0    0    0    0
//0    0    0    0    0    0    0
//0    0    0    0    0    0    0
//0    0    0    0    0    0    0
//0    0    0    0    0    0    0
//0    0    2    0    0    0    0 
//然后会发现我们无法全部走完，也正符合贪心策略，“只注重眼前的利益”，因此此题使用二维dp绝非正解，上代码：
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int dx[]={0,1},dy[]={1,0},n,mp[N][N];
int dp[N][N],res,ans;
int main()
{
    cin>>n;
    int a,b,c;
    while(cin>>a>>b>>c&&a+b+c>0) mp[a][b]=c;
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++) cout<<mp[i][j]<<' ';
//        cout<<endl;
//    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=max(dp[i-1][j]+mp[i][j],dp[i][j-1]+mp[i][j]);
    res=dp[n][n],ans=dp[n][n];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(dp[i][j]==res&&dp[i][j]!=0) res-=mp[i][j],mp[i][j]=0,i=0,j=0;
        }
    }
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=max(dp[i-1][j]+mp[i][j],dp[i][j-1]+mp[i][j]);
    cout<<ans+dp[n][n];
    return 0;
}

//正确思路:  
//四维dp,用ijkl表示思维,ij表示第一遍走的,kl表示第二遍走的,然后进行n^4的dp
//如果遇到相同的点就直接减去 
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n,m,dp[N][N][N][N],mp[N][N];
int main()
{
    cin>>n;
    int a,b,c;
    while(cin>>a>>b>>c&&a+b+c>0) mp[a][b]=c;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                for(int l=1;l<=n;l++){
                    dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],max(dp[i-1][j][k][l-1],dp[i][j-1][k][l-1])),dp[i][j-1][k-1][l])+mp[i][j]+mp[k][l];
                    if(i==k&&j==l) dp[i][j][k][l]-=mp[k][l];
                }
    cout<<dp[n][n][n][n];
    return 0;
}