LightOJ 1422：Halloween Costumes（区间DP入门）

http://lightoj.com/volume_showproblem.php?problem=1422

题意：去参加派对，有n场派对，每场派对要穿第wi种衣服，可以选择外面套一件，也可以选择脱掉。问至少需要穿多少次衣服。

思路：开始学一下区间DP。学习资料

区间dp就是枚举区间的长度，然后在起点i到起点+长度j这段区间里面，用一个分割线分隔开，分为左右两边，然后通过左右两边的子问题去更新当前枚举的区间的结果。复杂度一般都为O（n^3）。

这里的题目就是一开始dp[i][i] = 1，代表初始的第i个派对需要穿1件衣服。

dp[i][j] = dp[i][k] + dp[k+1][j]。如果 wi == wj 的话，那么代表在起点穿该件衣服，终点可以脱掉之前的衣服用之前的衣服。所以答案需要-1。

 #include <bits/stdc++.h>

 using namespace std;

 #define N 105

 #define INF 0x3f3f3f3f

 int w[N], dp[N][N];

 int main() {

     int t, cas = ;

     scanf("%d", &t);

     while(t--) {

         int n;

         scanf("%d", &n);

         memset(dp, INF, sizeof(dp));

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

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

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

                 int j = i + len;

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

                     if(dp[i][j] > dp[i][k] + dp[k+][j]) dp[i][j] = dp[i][k] + dp[k+][j];

                 if(w[i] == w[j]) dp[i][j]--;

             }

         }

         printf("Case %d: %d\n", ++cas, dp[][n]);

     }

     return ;

 }

巴特西

LightOJ 1422：Halloween Costumes（区间DP入门）

最新文章

热门文章