P1541 乌龟棋 线性DP

· · 个人记录

题目简介

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

思路

首先可以想到暴力做法：

然后用五重循环代表每个阶段。 别忘了初始化，$ dp[1][0][0][0][0]=a[1] 
if(i-1>=0) dp[i][f1][f2][f3][f4]=max(dp[i][f1][f2][f3][f4],dp[i-1][f1-1][f2][f3][f4]);
if(i-2>=0) dp[i][f1][f2][f3][f4]=max(dp[i][f1][f2][f3][f4],dp[i-2][f1][f2-1][f3][f4]);
if(i-3>=0) dp[i][f1][f2][f3][f4]=max(dp[i][f1][f2][f3][f4],dp[i-3][f1][f2][f3-1][f4]);
if(i-4>=0) dp[i][f1][f2][f3][f4]=max(dp[i][f1][f2][f3][f4],dp[i-4][f1][f2][f3][f4-1]);
dp[i][f1][f2][f3][f4]+=a[i];

这样做可以拿50分，时间、空间都会超。

但是我们可以发现，i 这个状态是没必要的。

因为我们可以有后四个状态推出 i 是多少，这样时空间都是 40^4 。

状态转移方程就这样表示：

int i=1+f1+f2*2+f3*3+f4*4; //细节加一 
if(f1>0) dp[f1][f2][f3][f4]=max(dp[f1][f2][f3][f4],dp[f1-1][f2][f3][f4]+a[i]);
if(f2>0) dp[f1][f2][f3][f4]=max(dp[f1][f2][f3][f4],dp[f1][f2-1][f3][f4]+a[i]);
if(f3>0) dp[f1][f2][f3][f4]=max(dp[f1][f2][f3][f4],dp[f1][f2][f3-1][f4]+a[i]);
if(f4>0) dp[f1][f2][f3][f4]=max(dp[f1][f2][f3][f4],dp[f1][f2][f3][f4-1]+a[i]);

结束，附上程序。

#include<bits/stdc++.h>
using namespace std;
int n,a[505],dp[45][45][45][45];
int m,f[5],b;
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n;i++) cin>>a[i];
    for(int i=1; i<=m;i++)
    {
        cin>>b;
        f[b]++;
    }
    dp[0][0][0][0]=a[1];
    for(int f1=0; f1<=f[1];f1++)
     for(int f2=0; f2<=f[2];f2++)
      for(int f3=0; f3<=f[3];f3++)
       for(int f4=0; f4<=f[4];f4++)
       {
        int i=1+f1+f2*2+f3*3+f4*4; //细节加一 
            if(f1>0) dp[f1][f2][f3][f4]=max(dp[f1][f2][f3][f4],dp[f1-1][f2][f3][f4]+a[i]);
            if(f2>0) dp[f1][f2][f3][f4]=max(dp[f1][f2][f3][f4],dp[f1][f2-1][f3][f4]+a[i]);
            if(f3>0) dp[f1][f2][f3][f4]=max(dp[f1][f2][f3][f4],dp[f1][f2][f3-1][f4]+a[i]);
            if(f4>0) dp[f1][f2][f3][f4]=max(dp[f1][f2][f3][f4],dp[f1][f2][f3][f4-1]+a[i]);
       }
    cout<<dp[f[1]][f[2]][f[3]][f[4]];
    return 0;
 }

总结

先对第一个或最后一个阶段分类讨论，找到最初的思路，然后想办法优化。

这道题的优化方式：去除一层可以被其它状态表示的状态。