[Acwing] 1027. 方格取数 计数DP

前言

传送门 : https://www.acwing.com/problem/content/1029/

看完题 i-1 j-1 推一下 再看一眼 傻了 两条？ 我还要记录一下 ？ 怎么记录啊

这题同时记录两个状态 是我没想到的

而且还可以优化一维 状态也好牛

思路

既然是两条 那么 直接 四个状态 走起 f [ i 1 ] [ j 1 ] [ i 2 ] [ j 2 ] f[i1][j1][i2][j2] f[i1][j1][i2][j2]

这状态也太多了吧 ~

我们考虑一下重复选到的点 i 1 + j 1 = = i 2 + j 2 i1+j1 == i2+j2 i1+j1==i2+j2

因此我们可以 令 k = i 1 + j 1 = i 2 + j 2 k = i1+j1 = i2+j2 k=i1+j1=i2+j2

因此状态就变成了三维的 f [ k ] [ i 1 ] [ i 2 ] f[k][i1][i2] f[k][i1][i2]

而 j 1 = k − i 1 , j 2 = k − i 2 j1 = k-i1 ,j2 = k-i2 j1=k−i1,j2=k−i2

因此我们的状态转移方程就是

f [ k ] [ i 1 ] [ i 2 ] = m a x ( f [ k − 1 ] [ i 1 − 1 ] [ i 2 − 1 ] + t , f [ k − 1 ] [ i 1 − 1 ] [ i 2 ] + t , f [ k − 1 ] [ i 1 ] [ i 2 − 1 ] + t , f [ k − 1 ] [ i 1 ] [ i 2 ] + t ) f[k][i1][i2] = {max}( f[k-1][i1-1][i2-1]+t,f[k-1][i1-1][i2]+t,f[k-1][i1][i2-1]+t,f[k-1][i1][i2]+t) f[k][i1][i2]=max(f[k−1][i1−1][i2−1]+t,f[k−1][i1−1][i2]+t,f[k−1][i1][i2−1]+t,f[k−1][i1][i2]+t)

CODE

#include 
using namespace std;
const int N  = 20;
int n;
int w[N][N],f[N*2][N][N];
void solve()
{
    cin>>n;
    int a,b,c;
    while(cin>>a>>b>>c,a||b||c) w[a][b] = c;

    for(int k=2; k