高维DP get ！

A4paper · 2018-07-09 17:52:02 · 个人记录

变态：

传送门

四维DP

可以说是很优秀了（就是变态）

有点抽象，不想多做解释。。。

总之，

四个维度是四张卡片打出的数量

然后背包

int m,n;
int One,Two,Thr,Fou;
int map[400],DP[45][45][45][45];

int main(void)
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)   cin >> map[i];
    for(int i=1,x;i<=m;i++)
    {
        cin >> x;
        switch(x){
            case 1: One++;  break;
            case 2: Two++;  break;
            case 3: Thr++;  break;
            case 4: Fou++;  break;
        }
    }
    DP[0][0][0][0] = map[1];
    for(int a=0;a<=One;a++)
    for(int b=0;b<=Two;b++)
    for(int c=0;c<=Thr;c++)
    for(int d=0;d<=Fou;d++)
    {
        int len = 1+a + b*2 + c*3 + d*4;
        if(a)   DP[a][b][c][d] = max(DP[a][b][c][d],DP[a-1][b][c][d]+map[len]);
        if(b)   DP[a][b][c][d] = max(DP[a][b][c][d],DP[a][b-1][c][d]+map[len]);
        if(c)   DP[a][b][c][d] = max(DP[a][b][c][d],DP[a][b][c-1][d]+map[len]);
        if(d)   DP[a][b][c][d] = max(DP[a][b][c][d],DP[a][b][c][d-1]+map[len]);
    }
    cout << DP[One][Two][Thr][Fou];
    return 0;
}

独秀：

传送门

一定要注意 k 的大小写啊！！！

#define c cnt^1
const int p = 1000000007;

int A,B,K;
bool cnt = 1;
char a[1005],b[205];
int f[2][205][205][2];

int main(void)
{
    cin >> A >> B >> K;
    scanf("%s%s",a+1,b+1);
    f[0][0][0][0] = f[1][0][0][0] = 1;
    for(int i=1;i<=A;i++,cnt^=1)
    for(int j=1;j<=B;j++)
    for(int k=1;k<=K;k++)
    {
        f[cnt][j][k][0] = (f[c][j][k][1] + f[c][j][k][0]) % p;
        if(a[i] == b[j])
            f[cnt][j][k][1]=(f[c][j-1][k][1]+(f[c][j-1][k-1][1]+f[c][j-1][k-1][0])%p)%p;
        else    f[cnt][j][k][1] = 0;
    }
    cout << (f[A&1][B][K][0]+f[A&1][B][K][1]) % p;
    return 0;
}

海星：

传送门

h 表示差值，uim 取数会使差值变小，小 A 取数会使差值变大，注意取模

int n,m,k,ans;
int map[MAXN][MAXN];
int f[MAXN][MAXN][20][2];

int main(void)
{
    cin >> n >> m >> k;
    k++;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        cin >> map[i][j];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        f[i][j][map[i][j]][0] = 1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    for(int h=0;h<=k;h++)
    {
        f[i][j][h][1] = (f[i][j][h][1]+f[i-1][j][(h+map[i][j])%k][0])  %p;
        f[i][j][h][1] = (f[i][j][h][1]+f[i][j-1][(h+map[i][j])%k][0])  %p;
        f[i][j][h][0] = (f[i][j][h][0]+f[i-1][j][(h-map[i][j]+k)%k][1])%p;
        f[i][j][h][0] = (f[i][j][h][0]+f[i][j-1][(h-map[i][j]+k)%k][1])%p;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        ans = (ans+f[i][j][0][1])%p;
    cout << ans;
    return 0;
}

强化：

传送门

对齐怪在此！！（这也许是玩我的世界的后遗症吧）

众所周知，一行或一列最多有 2 个炮

f [ i ] [ j ] [ k ] 表示找到第 i 行，共有 j 列有 1 个炮，共有 k 列有 2 个炮 ，那么，共有 m - j - k 列没有炮

接下来是极具挑战性的 6 个方程，一个一个解释吧 （取模部分省略）

一、

f[i+1][j][k] += f[i][j][k];

这种状态的意思是，每行的炮数都没有发生变化，很简单，就是什么也不做，直接下传上一行状态

二、

if(j > 0)
    f[i+1][j-1][k+1] += f[i][j][k] * j;

如果在这一行放置前有 1 个炮的列数大于 0 ，那么就有权利在某一列再放一个，使它进化到第三维上去，

由于每一列都有这样的机会，所以方案数要 * j

三、

if(j > 1)
    f[i+1][j-2][k+2] += f[i][j][k]*C(j);

如果在这一行放置前有 1 个炮的列数大于 1 ，那么就有权利在某两列放两个，使两列进化到第三维上去，

显然，用组合数求就好了，不过取两个数是可以用等差的，详见 code

由于每行最多放两个，所以不需要考虑大于 2 及以上的情况。

四、

if(m-j-k > 0)
    f[i+1][j+1][k] += f[i][j][k]*(m-j-k);

如果在这一行放置前有 0 个炮的列数大于 0 ，那么就有权利在某一列再放一个，使它进化到第二维上去，

由于每一列都有这样的机会，所以方案数要 * ( m - j - k )

五、

if(m-j-k > 1)
    f[i+1][j+2][k] += f[i][j][k]*C(m-j-k);

如果在这一行放置前有 0 个炮的列数大于 1 ，那么就有权利在某两列放两个，使两列进化到第三维上去，

同样的，也用到了组合数。

六、

if(m-j-k>0 && j>0)
    f[i+1][j][k+1] += f[i][j][k]*j*(m-j-k);

当然，如果在这一行放置前有 0 个炮的列数大于 0 ，且有 1 个炮的列数大于 0 ，那么它也有权利在某两列列再放两个，使它们分别进化到第二维和第三维上去，

由于必须要选一列没有炮，一列有一个炮，所以方案要 j ( m - j - k )

LL f[105][105][105];    //在第 i 行，有 j 列有 1 个炮，有 k 列有 2 个炮 

int C(int m)    {return m*(m-1)/2;}

int main(void)
{
    cin >> n >> m;
    f[0][0][0] = 1;
    for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++)
    for(int k=0;j+k<=m;k++)
    {
        if(!f[i][j][k]) continue;
                        f[i+1][j  ][k  ] = (f[i+1][j  ][k  ]+f[i][j][k]          ) % p;
        if(j > 0)       f[i+1][j-1][k+1] = (f[i+1][j-1][k+1]+f[i][j][k]*j        ) % p;
        if(j > 1)       f[i+1][j-2][k+2] = (f[i+1][j-2][k+2]+f[i][j][k]*C(j)     ) % p;
        if(m-k-j > 0)   f[i+1][j+1][k  ] = (f[i+1][j+1][k  ]+f[i][j][k]*(m-k-j)  ) % p;
        if(m-k-j > 1)   f[i+1][j+2][k  ] = (f[i+1][j+2][k  ]+f[i][j][k]*C(m-k-j) ) % p;
        if(m-k-j>0&&j>0)f[i+1][j  ][k+1] = (f[i+1][j  ][k+1]+f[i][j][k]*(m-k-j)*j) % p;
    }
    for(int i=0;i<=m;i++)
    for(int j=0;j+i<=m;j++)
        ans = (ans+f[n][i][j]) % p;
    cout << ans;
    return 0;
}

优化：

传送门

前排提示：为了叙述方便，我们把传纸条过程中时位置靠左的同学称为 1 号点，把位置靠右的同学称为 2 号点。

那么一种方法就是四维 DP ，前两维表示 1 号点的坐标，后两维表示 2 号点的坐标。这种算法是 n^4 的，实在是太蠢了！我们要优化它。

首先，要理解这么几件事，两个人互相传纸条可以看成由一个人同时传两张纸条，由于纸条只能向下或右传，对于每一时刻，纸条的位置都在一条斜线上，如图：

图怎么这么小，我的妈耶！如果影响体验的话就自己画一下吧。。。

对于一条斜线上的每个点，横纵坐标和都是相等的，所以只要表示出这个和以及一个纵左标（或者横坐标，看习惯）就可以表示一个点。

此时开三维数组 f[s][i][j] 表示和为 s 时，1 号点纵坐标为 i ，2 号点纵坐标为 j 时的最大值。这样就压掉了一维，比以前机智多了。

转移：

至于转移方程，对于一个点，只能从上或左转移而来，所以有两个转移方程取 max ，那么两个点的话自然就是四个，再加上自己就是五个。

max(f[s][i][j],
max(
    max(f[s-1][i][j],f[s-1][i-1][j-1]),
    max(f[s-1][i-1][j],f[s-1][i][j-1])
));

判重：

这是一个必须要考虑的边界问题，因为两份纸条不能从同一个人手中传出（除了起点，不要抬杠），之前没有提这里是为了降低思维难度，那么枚举 2 号点的范围就是 i+1 到 m

int main(void)
{
    memset(f,-1,sizeof(f));
    f[2][1][1] = 0;
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        cin >> map[i][j];
    for(int s=3;s<n+m;s++)
    for(int i=1;i<m;i++)
    for(int j=i+1;j<=m;j++)
    {
        int tot = max(f[s][i][j],max(
            max(f[s-1][i][j],f[s-1][i-1][j-1]),
            max(f[s-1][i-1][j],f[s-1][i][j-1])
            ));
        if(tot == -1) continue;
        f[s][i][j] = tot+map[s-i][i]+map[s-j][j];
    }
    cout << f[m+n-1][m-1][m];
    return 0;
}

填坑：高清大图请看这里（丑陋的博客园）