LightOJ-1422 区间dp

发布于 2020-03-19  1517 次阅读


题意

小灰灰参加圣诞节的一些派对,并且需要穿上对应派对的衣服,所以他需要多次换衣服,为了方便,他可以选择脱掉一些衣服或者穿上新衣服,比如说,他穿着超人的衣服,外面又穿着死侍的衣服,当他要参加超人服装派对时,他可以选择脱掉死侍的衣服(因为死侍衣服的里面有超人的衣服),或者他可以在穿一件超人的衣服,小灰灰是个爱干净的人,当他脱下死侍的衣服后,如果需要再穿死侍的衣服,他会选择再穿一件新的。(如果他先穿A衣服,又穿上B衣服,再穿一件C衣服,如果他想让最外面的衣服是A,他可以选择直接穿一件A,或者先把C脱掉,再把B脱掉)。

题解

/*
O(n3)
区间dp
dp起点为起点和终点相同的为1
然后开始枚举中间点,
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
如果起点和终点的值一样就在枚举前设置
dp[i][j]=dp[i][j-1]
*/
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 240;
int n;
int num[maxn], dp[maxn][maxn];
int main()
{
    ios::sync_with_stdio(0);
    // freopen("a.in", "r", stdin);
    int __t, dd = 1;
    cin >> __t;
    while (__t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> num[i];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++)
            dp[i][i] = 1;

        for (int len = 1; len < n; len++)
        {
            for (int i = 1; i + len <= n; i++)
            {
                int j = i + len;
                if (num[i] == num[j])
                    dp[i][j] = dp[i][j - 1];
                for (int k = i; k < i + len; k++)
                {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
        cout << "Case " << dd++ << ": " << dp[1][n] << endl;
    }

    return 0;
}


Humble Halten