Light OJ 1422-ハロウィンCostumes

5200 ワード
OS
テーマリンク:http://lightoj.com/volume_showproblem.php？problem=1422
とても簡単な区間DPの入門問題です.最初はこの問題を長い間考えましたが、思い出せませんでした.後のいくつかの区間DPをして戻ってきたらやっと分かりました.
区間DPは、記憶化探索および直接DPの方法を用いて書くことができる.
この問題の状態は方程式を変えます.
dp[i][j]=min(1+dp[i＋1][j],dp[i＋1][k-1]+dp[k][j]  (   a[i]==a[k]  i初期化に注意します
/*

 * Light OJ 1422 - Halloween Costumes

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

 *    DP   。

 *       i j，dp[i][j].

 *      i   ，   i      i  ，    dp[i+1][j]+1 

 *     i+1~j   k，  a[i]==a[k].  dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j])

 *      i           ，      1， dp[k][j]

 *      

 */



#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <string.h>

using namespace std;

const int MAXN=110;

int a[MAXN];

int dp[MAXN][MAXN];



int main()

{

    int T;

    int n;

    scanf("%d",&T);

    int iCase=0;

    while(T--)

    {

        iCase++;

        scanf("%d",&n);

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

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

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

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

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

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

        for(int i=n-1;i>=1;i--)//  DP   

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

            {

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

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

                    if(a[i]==a[k])//    

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

            }

        printf("Case %d: %d
",iCase,dp[1][n]);

    }

    return 0;

}
 
 
 
 
Javascriptで編集枠とTextAreaのカーソルに文字を挿入し、連続挿入をサポートします.