チェック数+メモ

方格は数を取ってメモを伝えます実はこの2つのテーマは同じです私达はテーマを见てみましょう
四角形にはN*Nの四角形図(N<=9)があり、その中のいくつかの四角形に正の整数を記入し、他の四角形には
人数0.下図のように(例を参照):
A 0 0 0 0 0 0 0 0 0 0 13 0 0 6 0 0 0 0 0 0 7 0 0 0 0 0 0 14 0 0 0 0 0 21 0 0 0 4 0 0 0 0 15 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . B
ある人は図の左上隅のA点から出発して、下へ歩くことができて、右へ行くことができて、右下隅のBに着くまで
点.歩いた道で、彼は四角い格子の中の数を取ることができます(取った後の四角い格子は数字0になります).
この人はA点からB点まで2回歩いて、取得した数の和を最大にするように2つのパスを見つけてみました.
伝纸条小渊と小轩は良い友达で同级生で、彼らはいっしょにいていつも话しきれない话题があります.ある素質の開拓活動の中で、クラスの同級生はm行n列の行列を作るように手配したが、小渕と小軒は行列の対角線の両端に配置されたので、彼らは直接話をすることができなかった.幸いなことに、彼らはメモを伝えることで交流することができます.メモは多くの学生を通じて相手の手に伝わり、小渕は行列の左上隅、座標(1,1)、小軒は行列の右下隅、座標(m,n)に座っている.小渕から小軒に伝わるメモは下または右にしか伝わらず、小軒から小渕に伝わるメモは上または左にしか伝わらない.
イベントの進行中、小渕は小軒にメモを渡したいと同時に、小軒に返事をしてほしいと望んでいた.クラスの中ですべての学友はすべて彼らを伝达することができて、しかし一回だけ彼らを助けることができて、つまりこの人が小渕が小軒のメモを渡した时に手伝うならば、小軒が小渕に渡した时に二度と手伝うことはありません.逆もまた然り.
もう一つ注意しなければならないことがあります.クラス全員が手伝ってくれる好感度が高い(注意:小渕と小軒の好意の程度は定義されておらず、入力時には0で表す)は、0-100の自然数で表すことができ、数が大きいほど好意を表すことができます.小渕と小軒はできるだけ好意の程度の高い学生を探してメモを伝えることを望んでいます.つまり、往復2つのパスの学生の好意の程度が最大になるように、往復2つのパスを見つけることができます.今、助けてください.小渕と小軒はこのような2つのパスを見つけた.////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////2番目の問題は左上隅を歩くことができます.これで1番目の問題と同じです.
私たちは1つの4次元数字でDPを行うと仮定して1回歩くと1つの格子の最適解が上と左で押し出されるので、状態遷移方程式はDP[i][j]=max(DP[i][j-1],DP[i-1][j])+map[i][j]で2回歩くことができます.しかし、繰り返してはいけません.今、2次元を加えると、状態遷移方程式はDP[i][j][k][l]=max(DP[i-1][j][k-1][l]、DP[i-1][j][k][l-1]、DP[ i][j-1][k-1][l]、DP[ i][j][k][l-1])+map[i][j]+map[k][l]に問題があります.同じ格子を歩くことはできないので、同じ格子を歩くと上の値を減算します.
グリッド数

#include 
#include 
using namespace std;
int map[999][999];
int dp[55][55][55][55];
int main()
{
    int n;

    scanf("%d",&n);

    while(1)
    {
        int x,y,c;

        scanf("%d%d%d",&x,&y,&c);

        if(!x&&!y&&!c) break;

        map[x][y]=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++)
        {
            int s1=max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]);
            int s2=max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]);

            int pls=map[i][j]+map[k][l];

            if(i==k&&j==l)
             pls-=map[i][j];

            dp[i][j][k][l]=max(s1,s2)+pls;
        }

    printf("%d",dp[n][n][n][n]);

    return 0;
} 

メモをとる

#include 
#include 
using namespace std;
int map[999][999];
int dp[55][55][55][55];
int main()
{
    int n,m;

    scanf("%d%d",&m,&n);

    for(int i=1;i<=m;i++)
     for(int j=1;j<=n;j++)
    {
        int c;

        scanf("%d",&c);

        map[i][j]=c;
    }

    for(int i=1;i<=m;i++)
     for(int j=1;j<=n;j++)
      for(int k=1;k<=m;k++)
       for(int l=1;l<=n;l++)
        {
            int s1=max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]);
            int s2=max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]);

            int pls=map[i][j]+map[k][l];

            if(i==k&&j==l)
             pls-=map[i][j];

            dp[i][j][k][l]=max(s1,s2)+pls;
        }

    printf("%d",dp[m][n][m][n]);

    return 0;
}