区间dp的典例

区间dp，属于dp的一种，顾名思义，便是对区间处理的dp，其中石子归并，括号匹配，整数划分最为典型。

（1）石子归并

dp三要素：阶段，状态，决策。

首先我们从第i堆石子到第j堆石子合并所花费的最小费用设为dp[i][j], 然后去想状态转移方程，dp[i][j]必然有两堆石子合并而来，那么我们很快就可以推出状态转移方程为dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s);(s为两堆石子的总和）

下面附上代码

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int N =  + ;

 int a[N], dp[N][N], n, sum[N];

 void work(){

     for(int l = ; l <= n; l ++){

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

             int j = i + l;

             for(int k = i; k <= j; k ++){

                 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+][j] + sum[j] - sum[i-]);

             }

         }

     }

     printf("%d\n", dp[][n]);

 }

 int main(){

     while(scanf("%d", &n) == ){

         memset(dp, 0x3f,sizeof(dp));

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

             scanf("%d", a + i);

             sum[i] = sum[i-] + a[i];

             dp[i][i] = ;

         }

         work();

     }

     return ;

 }

当然还有变形题

思路差不多只不过把两个数的和改成积（ps:在处理前缀和的时候千万别取余，否则可能出现负数）

附上代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int N =  + ;

 int a[N], dp[N][N], n, ans, sum[N];

 void  work(){

     for(int l  = ; l <= n; l ++){

         for(int i = ; i <= n - l + ; i ++){

             int j = i + l - ;

             for(int k = i; k < j; k ++){

                 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+][j] + ((sum[j] - sum[k])%)*((sum[k] - sum[i-])%));

             }

         }

     }

     printf("%d\n", dp[][n]);

 }

 int main(){

     while(scanf("%d", &n) == ){

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

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

                 dp[i][j] = ( << );

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

             scanf("%d", a + i);

             sum[i] = sum[i-] + a[i];

             dp[i][i] = ;

         }

         work();

     }

     return ;

 }

（2）括号匹配

这题解释括号匹配的例题，只要找到这个字符串中括号最大匹配量t,就可以得出答案，设长度为l,则ans = l - t;

我们设dp[i][j] 为第i位到第j位最大的括号匹配量，则他的转移方程为

dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);

当然如果第i位刚好与第j位刚好匹配

则dp[i][j] = dp[i+1][j-1] + 2;

下面附上代码

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 string s;

 int n, dp[][];

 int main(){

     int T;

     scanf("%d", &T);

     while(T--){

         cin >> s;

         memset(dp, , sizeof(dp));

         for(int l = ; l < s.size(); l ++){

             for(int i = ; i + l < s.size(); i ++){

                 int j = i + l;

                 if(s[i] == '(' && s[j] == ')')

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

                 if(s[i] == '[' && s[j] == ']')

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

                 for(int k = i; k <= j; k ++){

                     dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+][j]);

                 }

             }

         }

         printf("%d\n", s.size() - dp[][s.size()-]);

     }

     return ;

 }

（3）整数划分

当初一看到这一题的时候感觉像是搜索题，仔细一想才明白是一道区间dp题，既然是dp，当然要先找到状态了，设dp[i][j]为前i位中存在j个乘号

我们以a[i][j]表示第i位到第j位的值，则可以推出状态转移方程为dp[i][j] = max(dp[i][j], dp[i][k] * a[k+1][j]);

附上代码

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 const int N =  + ;

 ll a[N][N], dp[N][N];

 int n, T, c[N];

 char s[N];

 void work(){

     for(int j = ; j < n; j ++){

         for(int i = ; i <= strlen(s); i ++){

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

                 if(j==)

                     dp[i][] = a[][i];

                 else

                     dp[i][j] = max(dp[i][j], dp[k][j-] * a[k+][i]);

                 /*for(int p = 1; p <= strlen(s); p ++){

                     for(int q = 0; q < n; q ++)

                         printf("%d ", dp[p][q]);

                     puts("");

                 }*/

             }

         }

     }

     printf("%lld\n", dp[strlen(s)][n-]);

 }

 int main(){

     scanf("%d", &T);

     while(T--){

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

         int flag = ;

         if(n > strlen(s)){

             printf("0\n");

             continue;

         }

         memset(a, , sizeof(a));

         memset(dp, , sizeof(dp));

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

             c[i+] = s[i] - '';

         for(int i = ; i <= strlen(s); i ++){

             for(int j = i; j <= strlen(s); j ++){

                     a[i][j] = a[i][j-] *  + c[i];

                 }

             }

         }

         /*for(int i = 1; i <= strlen(s); i ++){

             for(int j = i; j <= strlen(s); j ++)

                 printf("%I64d ", a[i][j]);

             puts("");

         }*/

         work();

     }

     return ;

 }

巴特西

区间dp的典例

最新文章

热门文章