动态规划：高维DP

例子当然是王八棋这道题，这道题以前是写烂了

先来一个大暴力，zlw教的暴力~~

 #include<iostream>

 using namespace std;

 const int maxn=,maxm=;

 int a[maxn],b[];

 int n,m;

 int ans=;

 int MAX(int x,int y)

 {

 return x>y?x:y;

 }

 void dfs(int dp,int pos,int tmp)

 {

 ans=MAX(ans,tmp);

 for(int i=;i<=;i++)

 if(b[i])

 {

 b[i]--;

 dfs(dp+,pos+i,tmp+a[pos+i]);

 b[i]++;

 }

 }

 int main()

 {

 cin>>n>>m;

 for(int i=;i<=n;i++)

 cin>>a[i];

 for(int i=;i<=m;i++)

 {

 int x;

 cin>>x;

 if(x==) b[]++;

 if(x==) b[]++;

 if(x==) b[]++;

 if(x==) b[]++;

 }

 dfs(,,a[]);

 cout<<ans<<endl;

 return ;

 }

当时真是幼稚地连搜索都写不利索

多维动态规划的意思就是状态有好几个维度，我们在定义状态的时候要开多维数组

这道题里面四种卡牌用了多少了是四种可行的状态，还有一个是当前走到了哪个格子，作为阶段

f[][][][][]，然后就是这样了，MLE

这道题的思路是把阶段这一维度压掉，因为其可以用其他的状态来表示

一般的想法是把别的状态压掉，其实同样也能A掉这道题

压掉状态还是自然一些，压掉阶段就不太自然了

即使看上去很自然的样子

总的来说，好题一道，出题人无敌

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int INF=0x7f7f7f7f;

 const int maxn=,maxm=;

 int n,m,a,b,c,d,ans;

 int t[maxn];

 int f[][][][];

 int main()

 {

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

     for(int i=;i<=n;i++) scanf("%d",&t[i]);

     int x;

     for(int i=;i<=m;i++)

     {

         scanf("%d",&x);

         if(x==) a++;

         if(x==) b++;

         if(x==) c++;

         if(x==) d++;

     }

     for(int i=;i<=a;i++)

         for(int j=;j<=b;j++)

             for(int k=;k<=c;k++)

                 for(int l=;l<=d;l++)

                 {

                     if(i!=) f[i][j][k][l]=max(f[i][j][k][l],f[i-][j][k][l]);

                     if(j!=) f[i][j][k][l]=max(f[i][j][k][l],f[i][j-][k][l]);

                     if(k!=) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-][l]);

                     if(l!=) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-]);

                     f[i][j][k][l]+=t[i+*j+k*+l*+];

                 }

     printf("%d",f[a][b][c][d]);

     return ;

 }

这是一个5D/0D压成了4D/0D的动态规划？

巴特西

动态规划：高维DP

最新文章

热门文章