light oj 1422 Halloween Costumes (区间dp)

题目链接：http://vjudge.net/contest/141291#problem/D

题意：有n个地方，每个地方要穿一种衣服，衣服可以嵌套穿，一旦脱下的衣服不能再穿，除非穿同样的一件新的，问在满足题目要求的穿衣顺序下最少需要准备几件衣服。

思路：区间dp

//这个是看的别人的代码理解的，但是按照自己理解的写的代码样例正确，但是结果怎么都是WA的，不知道为什么，等我问问学长搞懂了再补题。//隔天改对了。

代码1：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define ll long long

const int maxn=1e2+;

const int INF=0x3f3f3f3f;

int dp[][];

int a[];

int main(){

    int T;

    scanf("%d",&T);

    for(int t=; t<=T; t++){

        int n;

        scanf("%d",&n);

        memset(dp,,sizeof(dp));

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

            scanf("%d",&a[i]);

            dp[i][i]=;

        }

        for(int d=; d<n; d++) ///区间长度

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

            int j=i+d;

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

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

            if(a[i]==a[k]) dp[i][j]=min(dp[i][j],dp[i+][k]+dp[k+][j]);

        }

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

    }

    return ;

}

代码2：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define ll long long

const int maxn=1e2+;

const int INF=0x3f3f3f3f;

int dp[][];

int a[];

int main(){

    int T;

    scanf("%d",&T);

    for(int t=; t<=T; t++){

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

        int n;

        scanf("%d",&n);

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

        for(int d=; d<n; d++) ///区间长度

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

            int j=i+d;

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

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

            if(a[i]==a[k]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);

        }

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

    }

    return ;

}

代码3：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define ll long long

const int maxn=1e2+;

const int INF=0x3f3f3f3f;

int dp[][];

int a[];

int main(){

    int T;

    scanf("%d",&T);

    for(int t=; t<=T; t++){

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

        int n;

        scanf("%d",&n);

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

        for(int j=; j<=n; j++) ///区间 i是头，j是尾

        for(int i=j-; i>=; i--){

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

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

            if(a[i]==a[k]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);

        }

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

    }

    return ;

}

巴特西

light oj 1422 Halloween Costumes (区间dp)

最新文章

热门文章