题意简述gcd 有nnn件衣服每件有颜色值cic_ici​和清洗时间tit_iti​。每天有个天气值wiw_iwi​每天他要选一件能穿的衣服不在清洗中舒适度是天气值乘颜色值。穿完后这件衣服要洗tit_iti​天包括当天才能再穿。问mmm天最大舒适度总和如果一定有哪天没衣服穿就输出 “gcd loves her clothes!”。思路分析nnn最大才四每件衣服洗的时间最多六天直接状态压缩动态规划就行了。状态用一个nnn位的数表示第iii位表示第iii件衣服还剩几天能穿000就是能穿。然后每天选一件能穿的对应位是000穿上后这位置成tit_iti​其他位如果小于零就减一。状态数最多(61)42401(61)^4 2401(61)42401种mmm最大两千直接两层循环暴力动态规划即可。实现先预处理出所有合法状态每位不超过对应的tit_iti​且至少一位是零。DPDPDP数组f[i][j]f[i][j]f[i][j]表示前iii天结束状态是jjj的最大舒适度。初始f[0][0]0f[0][0] 0f[0][0]0其他负无穷。转移枚举第 i 天开始前的状态jjj如果jjj的第kkk位是零就可以穿第 k 件得到新状态modify(j,k)modify(j, k)modify(j,k)然后更新f[i1][新状态]f[i1][新状态]f[i1][新状态]。最后扫一遍f[m][所有状态]f[m][所有状态]f[m][所有状态]取最大值如果全是负无穷就输出无解。状态数O((max(t1))n)O((max(t1))^n)O((max(t1))n)转移O(n∗状态数∗m)O(n * 状态数 * m)O(n∗状态数∗m)稳过。具体的状态:状态用一个十进制数字表示这个数字的位数等于衣服的数量。每个位上的数字0-9对应一件衣服的剩余清洗时间即清洗后还能穿着的剩余天数。例如如果有3件衣服状态数字如123表示第一件衣服剩余1天、第二件剩余2天、第三件剩余3天。状态必须满足两个合法性条件每个位上的数字不能超过对应衣服的最大清洗时间即不能超限。至少有一个位上的数字为0表示至少有一件衣服可以穿着否则无法进行清洗操作。关键操作获取状态位值有一个函数用于从状态数字中提取指定位置的位值即第k件衣服的剩余清洗时间。例如从状态123中提取第2位得到2。修改状态当选择清洗第k件衣服时状态会更新第k件衣服的剩余清洗时间重置为其最大清洗时间。其他衣服的剩余清洗时间各减1如果当前值大于0如果为0则保持0。例如如果状态为102衣服数量为3选择清洗第2件衣服假设其最大清洗时间为3新状态变为031第1位从1减为0第2位重置为3第3位保持2减为1。动态规划过程动态规划使用一个二维数组存储中间结果其中第一维表示天数第二维表示状态。数组的值表示在该天数和状态下的最大累计收益。初始化读取输入衣服数量、天数、每件衣服的清洗成本数组、每件衣服的最大清洗时间数组、每天的权重数组。生成所有合法状态枚举所有可能的n位十进制数n为衣服数量过滤掉非法状态即不满足上述合法性条件的并将合法状态存储在一个列表中。初始化动态规划数组设置第0天初始状态的收益为0其他状态收益为负无穷大表示不可达。状态转移从第0天开始逐天更新状态。对于每一天遍历所有合法状态。对于每个状态遍历每件衣服如果该衣服的剩余清洗时间为0即可以清洗则计算新状态通过修改函数更新。更新收益新收益 当前收益 当天的权重值 × 该衣服的清洗成本。存储新状态下的最大收益使用最大值函数更新。状态转移公式可以表示为新收益当前收益当天权重×衣服成本 \text{新收益} \text{当前收益} \text{当天权重} \times \text{衣服成本}新收益当前收益当天权重×衣服成本其中新状态通过修改函数获得。结果输出在所有天数结束后遍历所有合法状态找出最后一天的最大收益值。如果最大收益仍为负无穷大表示没有可行方案则输出错误信息例如“gcd loves her clothes!”表示调度失败。否则输出计算出的最大收益值。算法特点该算法使用状态压缩技术将多件衣服的状态编码为一个数字减少内存使用。动态规划的时间复杂度与状态数量相关状态总数最多为10n10^n10nn为衣服数量因此在衣服数量较小时高效。核心挑战在于状态转移的设计确保每次清洗操作后状态更新正确并维护收益最大化。代码#includealgorithm#includeiostream#includecstring#includecstdio#includevector#includecmath#definerep(i,a,b)for(inti(a);i(b);i)usingnamespacestd;usingLLlonglong;constintN2010;intn,m;intc[N],t[N],w[N];LL f[N][7000];vectorintstate;intget(intx,intk){// 取出 x 的第 k 位intres;while(k)resx%10,x/10,k--;returnres;}boolcheck(ints){// 判断状态 s 是否可用// 判断条件1. 没有一位大于它最大的清洗时间// 2. 必须有至少以为是 0否则 gcd 将没有衣服穿for(inti1;in;i)if(get(s,i)t[i])returnfalse;for(inti1;in;i)if(!get(s,i))returntrue;returnfalse;}intmodify(ints,intk){// 改动 s 的第 k 位// 即其他衣服的清洗时间 - 1第 k 天的重置位 t[k]intans0;for(intin;i;i--)if(ik)ansans*10t[k];elseansans*10(get(s,i)0?get(s,i)-1:0);returnans;}intmain(){scanf(%d%d,n,m);for(inti1;in;i)scanf(%d,c[i]);for(inti1;in;i)scanf(%d,t[i]);for(inti1;im;i)scanf(%d,w[i]);for(inti0;ipow(10,n);i)// 枚举可用状态if(check(i))state.push_back(i);// 并存储memset(f,-0x7f,sizeoff);f[0][0]0;for(inti0;im;i)for(autoj:state)for(intk1;kn;k)if(f[i][j]!-0x7f7f7f7f!get(j,k))f[i1][modify(j,k)]max(f[i1][modify(j,k)],f[i][j]w[i1]*c[k]);LL res-0x7f7f7f7f;for(autoi:state)resmax(res,f[m][i]);if(res-0x7f7f7f7f)puts(gcd loves her clothes!);elseprintf(%lld\n,res);return0;}