P4928 [MtOI2018] 衣服？身外之物！题解
题意简述
gcd 有nnn件衣服，每件有颜色值cic_ici和清洗时间tit_iti。每天有个天气值wiw_iwi，每天他要选一件能穿的衣服（不在清洗中），舒适度是天气值乘颜色值。穿完后这件衣服要洗tit_iti天（包括当天）才能再穿。问mmm天最大舒适度总和，如果一定有哪天没衣服穿就输出 “gcd loves her clothes!”。
思路分析
nnn最大才四，每件衣服洗的时间最多六天，直接状态压缩动态规划就行了。状态用一个nnn位的数表示，第iii位表示第iii件衣服还剩几天能穿（000就是能穿）。然后每天选一件能穿的（对应位是000），穿上后这位置成tit_iti，其他位如果小于零就减一。
状态数最多(6+1)4=2401(6+1)^4 = 2401(6+1)4=2401种，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[i+1][新状态]f[i+1][新状态]f[i+1][新状态]。
- 最后扫一遍f[m][所有状态]f[m][所有状态]f[m][所有状态]取最大值，如果全是负无穷就输出无解。
- 状态数O((max(t+1))n)O((max(t+1))^n)O((max(t+1))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^n10n（n为衣服数量），因此在衣服数量较小时高效。
核心挑战在于状态转移的设计，确保每次清洗操作后状态更新正确，并维护收益最大化。
代码
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#definerep(i,a,b)for(inti=(a);i<=(b);i++)usingnamespacestd;usingLL=longlong;constintN=2010;intn,m;intc[N],t[N],w[N];LL f[N][7000];vector<int>state;intget(intx,intk){// 取出 x 的第 k 位intres;while(k)res=x%10,x/=10,k--;returnres;}boolcheck(ints){// 判断状态 s 是否可用// 判断条件：1. 没有一位大于它最大的清洗时间// 2. 必须有至少以为是 0，否则 gcd 将没有衣服穿for(inti=1;i<=n;i++)if(get(s,i)>t[i])returnfalse;for(inti=1;i<=n;i++)if(!get(s,i))returntrue;returnfalse;}intmodify(ints,intk){// 改动 s 的第 k 位// 即：其他衣服的清洗时间 - 1，第 k 天的重置位 t[k]intans=0;for(inti=n;i;i--)if(i==k)ans=ans*10+t[k];elseans=ans*10+(get(s,i)>0?get(s,i)-1:0);returnans;}intmain(){scanf("%d%d",&n,&m);for(inti=1;i<=n;i++)scanf("%d",&c[i]);for(inti=1;i<=n;i++)scanf("%d",&t[i]);for(inti=1;i<=m;i++)scanf("%d",&w[i]);for(inti=0;i<pow(10,n);i++)// 枚举可用状态if(check(i))state.push_back(i);// 并存储memset(f,-0x7f,sizeoff);f[0][0]=0;for(inti=0;i<m;i++)for(autoj:state)for(intk=1;k<=n;k++)if(f[i][j]!=-0x7f7f7f7f&&!get(j,k))f[i+1][modify(j,k)]=max(f[i+1][modify(j,k)],f[i][j]+w[i+1]*c[k]);LL res=-0x7f7f7f7f;for(autoi:state)res=max(res,f[m][i]);if(res==-0x7f7f7f7f)puts("gcd loves her clothes!");elseprintf("%lld\n",res);return0;}