【HDU 6017】 Girls Love 233 （DP）

【分析】

　　考虑交换完之后的序列的样子：

　　假设是2333233->2333332

　　只考虑2的移动就好了，肯定是第一个2对应末状态第一个2，以此类推。。。

　　所以DP考虑2填在什么位置就好了。

　　f[i][j][k][p]表示填了i个数，有j个2，花费了k，p是最后几个数的状态。

　　0表示没有，1表示有‘2’，2表示有’23‘。

　　然后直接状态转移就好了【T那么大理论上不是过不了的吗？？

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define INF 0xfffffff

 int mymax(int x,int y) {return x>y?x:y;}

 int f[][][][];

 int pos[];

 char s[];

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         int n,m,sm=;

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

         scanf("%s",s+);

         for(int i=;i<=n;i++) if(s[i]=='') pos[++sm]=i;

         // memset(f,0,sizeof(f));

         for(int i=;i<=n;i++) for(int j=;j<=n;j++) for(int k=;k<=m;k++) f[i][j][k][]=f[i][j][k][]=f[i][j][k][]=-INF;

         f[][][][]=;

         int ans=;

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

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

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

           {

                 int ad=*abs(i-pos[j+]);

                 f[i][j+][k+ad][]=mymax(f[i][j+][k+ad][],f[i-][j][k][]);

                 f[i][j+][k+ad][]=mymax(f[i][j+][k+ad][],f[i-][j][k][]);

                 f[i][j+][k+ad][]=mymax(f[i][j+][k+ad][],f[i-][j][k][]);

                 f[i][j][k][]=mymax(f[i][j][k][],f[i-][j][k][]);

                 f[i][j][k][]=mymax(f[i][j][k][],f[i-][j][k][]);

                 f[i][j][k][]=mymax(f[i][j][k][],f[i-][j][k][]+);

                 if(j==sm)

                 {

                     ans=mymax(ans,f[i][j][k][]);

                     ans=mymax(ans,f[i][j][k][]);

                     ans=mymax(ans,f[i][j][k][]);

                 }

           }

         printf("%d\n",ans);

     }

     return ;

 }

2017-04-19 10:38:30