LightOJ 1422 Halloween Costumes(区间DP)-白红宇

LightOJ 1422 Halloween Costumes(区间DP)

阅读量：4541 次

发布时间：2019-06-08

本文共 1216 字，大约阅读时间需要 4 分钟。

题目链接：

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

解题思路：

初始化dp[i][i]=1,表示一场派穿一件衣服，设dp[i][j]表示i~j最少需要穿几次衣服，

得到状态转移方程：dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])(i<=k<j)

若a[i]==a[j]那么代表在起点穿该件衣服，终点可以脱掉之前的衣服用之前的衣服。所以答案需要-1。

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              11 #include
               
                12 #include
                
                 13 #define lc(a) (a<<1)14 #define rc(a) (a<<1|1)15 #define MID(a,b) ((a+b)>>1)16 #define fin(name) freopen(name,"r",stdin)17 #define fout(name) freopen(name,"w",stdout)18 #define clr(arr,val) memset(arr,val,sizeof(arr))19 #define _for(i,start,end) for(int i=start;i<=end;i++)20 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);21 using namespace std;22 typedef long long LL;23 const int N=5e2+5;24 const int INF=0x3f3f3f3f;25 const double eps=1e-10;26 27 int a[N];28 int dp[N][N];29 30 int main(){31 int t,n,cas=0;32 cin>>t;33 while(t--){34 cin>>n;35 for(int i=1;i<=n;i++){36 cin>>a[i];37 dp[i][i]=1; //一开始dp[i][i] = 1，代表初始的第i个派对需要穿1件衣服。38 }39 for(int len=1;len