LightOJ 1422 Halloween Costumes 动态规划 - c++编程基础

区间DP，鼻祖题目，认知了什么事区间DP，题意有点难理解，有N个宴会，对于每一个宴会，女猪脚都要穿一种礼服，礼服可以套着穿，但是脱了的不能再用，参加宴会必须按顺序来，从第一个到第N个，问参加这些宴会最少需要几件礼服，拿第一个案例来说把

1 2 1 2，有4个宴会，第一个需要礼服种类为1，第二个需要礼服种类为2，以此往下推：

参加第一个宴会时穿礼服1，参加第二个时，礼服1不要脱下，直接把礼服2套在外面，参加第三个的时候把礼服2脱下即可，参加第四个则需要一件新的礼服了

区间DP的状态转移方程大致不变，推的话状态从后往前更新，因为后面有相同的礼服种类会产生影响，从前面来不知行不行，但是肯定很麻烦，

状态转移：1：dp[i][j] = dp[i+1][j]，区间增加一个先直接判断需要多一件，然后进入第二状态的来判定

2：dp[i][j] = min(dp[i][j],dp[i+1][k-1] + dp[k][j]),这个是第i个宴会需要的礼服与第k个宴会需要的礼服一样，所以只需要选一件即可，所以后面找的是 dp[i+1][k-1]+dp[k][j]，来判断到底哪个小

还有对了，曾经我一直纠结于区间DP的边界值，大多数情况下，找最小，其实区间的DP值可以设为 i,j的区间长度即可，

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[1000 + 5][1000 + 5]; int num[1000 + 5]; void clear() { memset(dp,0,sizeof(dp)); memset(num,0,sizeof(num)); } int main() { int t; int n; int Case = 0; scanf("%d",&t); while(t--) { clear(); scanf("%d",&n); for(int i=0;i
                    
                     =0;i--) { for(int j=i+1;j