sdut1650I-Keyboard(dp)

题目大意就相当于跟你一串字符串让你截成k段使总体的值最小

想法是递归的递归太慢可以转换为递推的

这样就有可以推出状态方程 dp[i][j] = max(dp[i][j],dp[i-1][g]+sum[g+1][j]+sum[1][g]-sum[1][j]); dp[i][j]表示总长度为j第i次截的最小值后面的sum[i][j]表示的就是从i开始作为第一个到j个的花费 o[i][j]保存路径

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #define INF 1e10

 using namespace std;

 char s[],ks[];

 #define LL long long

 LL dp[][],p[],sum[][];

 int o[][],pa[];

 int main()

 {

     //freopen("data1.in","r",stdin);

     //freopen("text.out","w",stdout);

     int t,k,i,j,l,g,kk=;

     cin>>t;

     while(t--)

     {

         memset(sum,,sizeof(sum));

         kk++;

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

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

         dp[i][j] = INF;

         cin>>k>>l;

         cin>>ks;

         cin>>s;

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

             cin>>p[i];

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

         {

             for(j = i; j <= l ; j++)

                 sum[i][j] = sum[i][j-]+p[j]*(j-i+);

         }

         for(i =  ;i <= k- ; i++)

             for(j = l ; j >=  ; j--)

                 for(g =  ; g < j ; g++)

                 {

                     if(dp[i][j]>dp[i-][g]+sum[][g]+sum[g+][j]-sum[][j])

                     {

                         dp[i][j] = dp[i-][g]+sum[][g]+sum[g+][j]-sum[][j];

                         o[i][j] = g;

                     }

                 }

         int x = k-,y = l;

         g = ;

         while(x)

         {

             pa[++g] = o[x][y];

             x--;y = pa[g];

         }

         printf("Keypad #%d:\n",kk);

         pa[g+] = ;

         for(i = g ;i >=  ;i--)

         {

             printf("%c: ",ks[k-i-]);

             for(j =pa[i+]+; j <= pa[i] ; j++)

             {

                 printf("%c",s[j-]);

             }

             puts("");

         }

         printf("%c: ",ks[k-]);

         for(j = pa[]+; j <= l ; j++)

         printf("%c",s[j-]);

         puts("");

         puts("");

     }

     return ;

 }

 /**************************************

     Problem id    : SDUT OJ 1650

     User name    : shang

     Result        : Accepted

     Take Memory    : 688K

     Take Time    : 200MS

     Submit Time    : 2014-02-15 11:17:10

 **************************************/

巴特西

sdut1650I-Keyboard(dp)

最新文章

热门文章