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

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2858

题意：给你n天需要穿的衣服的样式，每次可以套着穿衣服，脱掉的衣服就不能再用了（可以再穿），问至少要带多少条衣服才能参加所有宴会

分组背包模板题：

 dp[i][j];若第j件穿，dp[i][j]=d[i][j-1]+1;

        若不穿，则可以想到，i到j-1区间内必须得有这件衣服，dp[i][j]=dp[i][k-1]+dp[k][j-1],i<=k<=j-1;a[j]==a[k];

代码：

#include
   
    #include
    
     #include
     
      using namespace std;const int maxn=110;int a[maxn];int dp[maxn][maxn];int main(){    int t,i,j,k;    while(cin>>t)    {        int p=1;        while(t--)        {            int n,m;            cin>>n>>m;            int i,j;            for(i=1;i<=n;i++)            {                cin>>a[i];            }            memset(dp,0,sizeof(dp));            for(i=1;i<=n;i++)                dp[i][i]=1;                //cout<<"haha"<
      
       =1;i--)                {                    for(j=i+1;j<=n;j++)                    {                        dp[i][j]=dp[i][j-1]+1;                        for(k=i;k<=j-1;k++)                        {                            if(a[j]==a[k])                            dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][j-1]);                        }                    }                }                cout<<"Case "<
       
        <<": "<
        
         <
        
       
      
     
    
   

转载地址：http://pygji.baihongyu.com/