本周主要学习内容：背包DP以及其他DP杂题。
9月8日
大地彩绘，爽读《1984》。
9月9日
1. P8742 [蓝桥杯 2021 省 AB] 砝码称重
(1) bitset法
开一个bitset b，其中b[j]表示重量j能否称到。
边界显然是b[0]=1。
对于每一个w[i]，b的每一位都应左移w[i]位，表示某一位所代表的砝码称重方案再加上第i个方案所构成的新方案所能称量的重量。
然后b的每一位再右移w[i]位，表示放在左盘，减去对应砝码的重量。注意左右位移的运算需要分别循环操作。
最后把重量0算上了，得减掉。
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=105,M=1e5+5;
bitset<M>b;
int n,w[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;b[0]=1;for(int i=1;i<=n;i++){cin>>w[i];b|=b<<w[i];}for(int i=1;i<=n;i++){b|=b>>w[i];}cout<<b.count()-1;return 0;
}
(2) 0-1背包法
DP数组可以用布尔类型记录状态：用f[i][j]表示枚举到第i个砝码时，能否称到重量j。
i枚举砝码序号，j从1枚举到所有砝码的质量总和，即所能称到的最大重量。
边界：f[i][w[i]]=1，因为对于每个砝码i，只放自己，肯定能称到自己的重量。
状态转移必须分类讨论。
-
当第i个砝码没放时：
f[i][j]=f[i-1][j]； -
当第i个砝码被放到右盘时：
f[i][j]=f[i-1][j-w[i]]，但仔细想想，考虑到前一个砝码被放到左盘或右盘的情况不同，所以加上绝对值，得到f[i][j]=f[i-1][abs(j-w[i])]； -
当第i个砝码被放到左盘时：
f[i][j]=f[i-1][j+w[i]]。
答案为f[n][j]的求和。
注：对于形如
if(f[i-1][j]){f[i][j]=1;
}
的代码，有更好的压行写法，即：
f[i][j]|=f[i-1][j];
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=105,M=1e5+5;
bool f[N][M];
int n,ans,sumj,w[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>w[i];sumj+=w[i];f[i][w[i]]=1;}for(int i=1;i<=n;i++){for(int j=sumj;j;j--){if(f[i-1][j]){f[i][j]=1;}if(f[i-1][abs(j-w[i])]){f[i][j]=1;}if(f[i-1][j+w[i]]){f[i][j]=1;}}}for(int j=1;j<=sumj;j++){ans+=f[n][j];}cout<<ans;return 0;
}
2. P2347 [NOIP 1996 提高组] 砝码称重
同上一题。
注意每次的bitset位移需要循环w[i]次，每次位移cost[i]（即对应的砝码重量）位。
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=7,M=1005,cost[]={0,1,2,3,5,10,20};
int n,w[N];
bitset<M>b;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);for(int i=1;i<=6;i++){cin>>w[i];}b[0]=1;for(int i=1;i<=6;i++){for(int j=1;j<=w[i];j++){b |= b<<cost[i];}}cout<<"Total="<<b.count()-1;return 0;
}
3. P5020 [NOIP 2018 提高组] 货币系统
好题。有点数学。
仍用f[j]表示是否能凑到金额j。
先把a数组从小到大排序，然后遍历a中的每一种货币，面值为a[i]。
如果使用前i种货币能够凑到i后面的货币面值，那么这个被凑到的货币面值是无用的。
比如样例：3 19 10 6，排序后为3 6 10 19，容易证明：用3可以凑到6，用3和10可以凑到19，所以10和19是无用的。（其实严格证明并不简单，但是列几组数据即可发现这一性质）
维护一个答案变量ans，初始值为面值种类数n，若出现一个无用的变量则将ans自减，最后输出每次的ans即可。
每次循环必须把f数组置0。
注意j的循环范围，没必要为从1到Σj，而仅从a[i]到a[n]即可。原因是，你只需要检验能否凑出货币面值的金额，而非所有能凑到的金额。
如果不缩小j的枚举范围，则会TLE后四个点，可见题的难度很大。
诡异的事情：如果换用bitset替代f维护，仍缩小j的枚举范围，仍会TLE后四个点，令人忍俊不禁。
code:
#include <bits/stdc++.h>
using namespace std;
constexpr int N=105,M=25005;
int Q,n,a[N],ans;
bool f[M];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>Q;while(Q--){memset(f,0,sizeof(f));f[0]=1;cin>>n;ans=n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);for(int i=1;i<=n;i++){if(f[a[i]]){ans--;}for(int j=a[i];j<=a[n];j++){f[j]|=f[j-a[i]];}}cout<<ans<<'\n';}return 0;
}
9月10日
1. P1096 [NOIP 2007 普及组] Hanoi 双塔问题
首先，这道题和标准Hanoi的思想基本相同，都是递归。
回顾一下标准Hanoi的思想：将n层Hanoi看成最下面的一片圆盘和上面的n-1层Hanoi，如此递下去，最终递到边界n=2，它的移动方式是显然的；然后再归回来，n层Hanoi的移动方式就可以被推出来了。
这道题和标准Hanoi的区别在于，每次移动一个圆盘，都要花费2步（我们把两个堆叠起来同等大小的圆盘看作一个圆盘），即递推式为：f[n]=2*f[n-1]+2。
对于边界，样例已给。
注意到这个递推式可能产生非常大的数值，所以我们采用高精度计算。因为我懒，所以直接写了个python来打表。
code:
#include <bits/stdc++.h>
using namespace std;
int n;
string lst[]={"0","2","6","14","30","62","126","254","510","1022","2046","4094","8190","16382","32766","65534","131070","262142","524286","1048574","2097150","4194302","8388606","16777214","33554430","67108862","134217726","268435454","536870910","1073741822","2147483646","4294967294","8589934590","17179869182","34359738366","68719476734","137438953470","274877906942","549755813886","1099511627774","2199023255550","4398046511102","8796093022206","17592186044414","35184372088830","70368744177662","140737488355326","281474976710654","562949953421310","1125899906842622","2251799813685246","4503599627370494","9007199254740990","18014398509481982","36028797018963966","72057594037927934","144115188075855870","288230376151711742","576460752303423486","1152921504606846974","2305843009213693950","4611686018427387902","9223372036854775806","18446744073709551614","36893488147419103230","73786976294838206462","147573952589676412926","295147905179352825854","590295810358705651710","1180591620717411303422","2361183241434822606846","4722366482869645213694","9444732965739290427390","18889465931478580854782","37778931862957161709566","75557863725914323419134","151115727451828646838270","302231454903657293676542","604462909807314587353086","1208925819614629174706174","2417851639229258349412350","4835703278458516698824702","9671406556917033397649406","19342813113834066795298814","38685626227668133590597630","77371252455336267181195262","154742504910672534362390526","309485009821345068724781054","618970019642690137449562110","1237940039285380274899124222","2475880078570760549798248446","4951760157141521099596496894","9903520314283042199192993790","19807040628566084398385987582","39614081257132168796771975166","79228162514264337593543950334","158456325028528675187087900670","316912650057057350374175801342","633825300114114700748351602686","1267650600228229401496703205374","2535301200456458802993406410750","5070602400912917605986812821502","10141204801825835211973625643006","20282409603651670423947251286014","40564819207303340847894502572030","81129638414606681695789005144062","162259276829213363391578010288126","324518553658426726783156020576254","649037107316853453566312041152510","1298074214633706907132624082305022","2596148429267413814265248164610046","5192296858534827628530496329220094","10384593717069655257060992658440190","20769187434139310514121985316880382","41538374868278621028243970633760766","83076749736557242056487941267521534","166153499473114484112975882535043070","332306998946228968225951765070086142","664613997892457936451903530140172286","1329227995784915872903807060280344574","2658455991569831745807614120560689150","5316911983139663491615228241121378302","10633823966279326983230456482242756606","21267647932558653966460912964485513214","42535295865117307932921825928971026430","85070591730234615865843651857942052862","170141183460469231731687303715884105726","340282366920938463463374607431768211454","680564733841876926926749214863536422910","1361129467683753853853498429727072845822","2722258935367507707706996859454145691646","5444517870735015415413993718908291383294","10889035741470030830827987437816582766590","21778071482940061661655974875633165533182","43556142965880123323311949751266331066366","87112285931760246646623899502532662132734","174224571863520493293247799005065324265470","348449143727040986586495598010130648530942","696898287454081973172991196020261297061886","1393796574908163946345982392040522594123774","2787593149816327892691964784081045188247550","5575186299632655785383929568162090376495102","11150372599265311570767859136324180752990206","22300745198530623141535718272648361505980414","44601490397061246283071436545296723011960830","89202980794122492566142873090593446023921662","178405961588244985132285746181186892047843326","356811923176489970264571492362373784095686654","713623846352979940529142984724747568191373310","1427247692705959881058285969449495136382746622","2854495385411919762116571938898990272765493246","5708990770823839524233143877797980545530986494","11417981541647679048466287755595961091061972990","22835963083295358096932575511191922182123945982","45671926166590716193865151022383844364247891966","91343852333181432387730302044767688728495783934","182687704666362864775460604089535377456991567870","365375409332725729550921208179070754913983135742","730750818665451459101842416358141509827966271486","1461501637330902918203684832716283019655932542974","2923003274661805836407369665432566039311865085950","5846006549323611672814739330865132078623730171902","11692013098647223345629478661730264157247460343806","23384026197294446691258957323460528314494920687614","46768052394588893382517914646921056628989841375230","93536104789177786765035829293842113257979682750462","187072209578355573530071658587684226515959365500926","374144419156711147060143317175368453031918731001854","748288838313422294120286634350736906063837462003710","1496577676626844588240573268701473812127674924007422","2993155353253689176481146537402947624255349848014846","5986310706507378352962293074805895248510699696029694","11972621413014756705924586149611790497021399392059390","23945242826029513411849172299223580994042798784118782","47890485652059026823698344598447161988085597568237566","95780971304118053647396689196894323976171195136475134","191561942608236107294793378393788647952342390272950270","383123885216472214589586756787577295904684780545900542","766247770432944429179173513575154591809369561091801086","1532495540865888858358347027150309183618739122183602174","3064991081731777716716694054300618367237478244367204350","6129982163463555433433388108601236734474956488734408702","12259964326927110866866776217202473468949912977468817406","24519928653854221733733552434404946937899825954937634814","49039857307708443467467104868809893875799651909875269630","98079714615416886934934209737619787751599303819750539262","196159429230833773869868419475239575503198607639501078526","392318858461667547739736838950479151006397215279002157054","784637716923335095479473677900958302012794430558004314110","1569275433846670190958947355801916604025588861116008628222","3138550867693340381917894711603833208051177722232017256446","6277101735386680763835789423207666416102355444464034512894","12554203470773361527671578846415332832204710888928069025790","25108406941546723055343157692830665664409421777856138051582","50216813883093446110686315385661331328818843555712276103166","100433627766186892221372630771322662657637687111424552206334","200867255532373784442745261542645325315275374222849104412670","401734511064747568885490523085290650630550748445698208825342","803469022129495137770981046170581301261101496891396417650686","1606938044258990275541962092341162602522202993782792835301374"};
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;cout<<lst[n];return 0;
}
2. P2851 [USACO06DEC] The Fewest Coins G
看似蓝题，实则背包板子。
状态定义：f[j]记录支付j元钱所需的最少纸币数，g[j]记录找回j元钱所需的最少纸币数。
显然，f在计算时使用多重背包，g则使用完全背包。
状态转移方程显然：f/g[j]=min(f/g[j-v[i]]+1)。
最后求f[j]+g[j-t]之和的最小值。
记得赋初始最大值。无解就是值没更新或者钱数总和太小，输出-1。
code:
#include <bits/stdc++.h>
using namespace std;
constexpr int N=105,M=1e7+5;
int n,t,v[N],c[N],sumj,maxj,ans=1e9,f[M],g[M];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));cin>>n>>t;for(int i=1;i<=n;i++){cin>>v[i];}for(int i=1;i<=n;i++){cin>>c[i];sumj+=v[i]*c[i];maxj=max(maxj,v[i]*v[i]);}if(sumj<t){cout<<"-1";return 0;}f[0]=g[0]=0;for(int i=1;i<=n;i++){for(int k=1;k<=c[i];k++){for(int j=maxj+t;j>=k*v[i];j--){f[j]=min(f[j],f[j-v[i]]+1);}}}for(int i=1;i<=n;i++){for(int j=v[i];j<=maxj;j++){g[j]=min(g[j],g[j-v[i]]+1);}}for(int j=t;j<=t+maxj;j++){ans=min(ans,f[j]+g[j-t]);}if(ans!=1e9){cout<<ans;}else{cout<<"-1";}return 0;
}
3. P1466 [USACO2.2] 集合 Subset Sums
对于一个1~n的连续整数集合A，如果要把A分成等和的两集合M和N，那么对于每一个M，对应的N都是确定且唯一的。所以我们只需要求M集合的个数即可。
同时又注意到，ΣM=ΣN=ΣA/2=(n*(n+1)/2)/2=n*(n+1)/4，所以我们只需要选取集合A中的若干元素，使得它们的和等于n*(n+1)/4即可。
于是对于每个元素，只有选或不选两种选择，那就是0-1背包。
定义f[i][j]表示前i个元素能凑到的和为j的方案总数。
显然有两种情况：
- 不选：
f[i][j]=f[i-1][j]； - 选：
f[i][j]+=f[i-1][j-i]，当且仅当j>=i。
边界显然是f[0][0]=1。
注意到一个性质：当n*(n+1)/2为奇数时，n*(n+1)/4必定带有小数部分，而整数部分凑不出来小数部分，所以这种情况没答案，直接输出0。
注意这题的时间复杂度实际上是三次方的，因为第二层循环循环了二次方次。
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=42,M=1e6+10;
int n,f[M];
signed main(){cin.tie(0)->sync_with_stdio(0);f[0]=1;cin>>n;for(int i=1;i<=n;i++){for(int j=n*(n+1)/2;j>=i;j--){f[j]+=f[j-i];}}cout<<((n*(n+1)/2)%2==0)*f[n*(n+1)/4]/2;return 0;
}
4. P1509 找啊找啊找GF
找GF时，时间是最珍贵的东西。
二维费用背包+次要性背包。
次要性背包是指，当某条件已经最优时，使另一条件也为最优的背包DP。
阅读题目，要求我们使得MM数量最多，且花费的总时间最少。
我们可以想到开两个背包数组来记录状态：
fnum[j][k]表示花费rp为j，花费rmb为k所泡到的最多MM数，ftim[j][k]表示花费rp为j，花费rmb为k所花的最少总时间。
状态转移方程显然是：
fnum[j][k]=fnum[j-rp[i]][k-rmb[i]]+1【1】；
ftim[j][k]=ftim[j-rp[i]][k-rmb[i]]+tim[i]【2】。
但要注意，当fnum[j-rp[i]][k-rmb[i]]+1>fnum[j][k]时，【1】才有资格转移，而且，在【1】转移的过程中，【2】也跟着转移；如果fnum[j-rp[i]][k-rmb[i]]+1==fnum[j][k]，那么证明泡到的MM数相等，那就选择时间最少的方案，即ftim[j][k]=min(ftim[j][k],ftim[j-rp[i]][k-rmb[i]]+tim[i])。
答案为ftim[r][m]。不用特判0。
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=105,M=1e3+10;
int n,rmb[N],rp[N],tim[N],m,r;
int fnum[M][M],ftim[M][M];
signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n;for(int i=1;i<=n;i++){cin>>rmb[i]>>rp[i]>>tim[i];}cin>>m>>r;for(int i=1;i<=n;i++){for(int j=r;j>=rp[i];j--){for(int k=m;k>=rmb[i];k--){if(fnum[j-rp[i]][k-rmb[i]]+1>fnum[j][k]){fnum[j][k]=fnum[j-rp[i]][k-rmb[i]]+1;ftim[j][k]=ftim[j-rp[i]][k-rmb[i]]+tim[i];}if(fnum[j-rp[i]][k-rmb[i]]+1==fnum[j][k]){ftim[j][k]=min(ftim[j][k],ftim[j-rp[i]][k-rmb[i]]+tim[i]);}}}}cout<<ftim[r][m];return 0;
}
5. P1855 榨取kkksc03
二维费用背包板子。
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=205,L=105;
int n,M,T,f[N][N],m[L],t[L];
signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n>>M>>T;for(int i=1;i<=n;i++){cin>>m[i]>>t[i];}for(int i=1;i<=n;i++){for(int j=M;j>=m[i];j--){for(int k=T;k>=t[i];k--){f[j][k]=max(f[j][k],f[j-m[i]][k-t[i]]+1);}}}cout<<f[M][T];return 0;
}
6. P1782 旅行商的背包【未完成】
7. P3985 不开心的金明【存疑】
9月11日
1. P2736 [USACO3.4] “破锣摇滚”乐队 Raucous Rockers
背包DP。
答案是乐曲最大数，所以我们的状态定义肯定存储乐曲最大数。
CD数目是有限的，而且根据题意，最后一张CD所存的乐曲时长，会影响当前所枚举的乐曲的存储方案。
不妨将上面两个因素融入状态定义：f[j][k]表示前j张光碟，最后一张光碟存储k分钟乐曲，所能存储的乐曲最大数。
对于第i个乐曲，有三种选择：
- 不选，
f[j][k]=f[j][k]； - 选，但最后一张放不下当前枚举的乐曲，所以需要新开一个CD，有
f[j][k]=f[j-1][T]+1； - 选，但最后一张能放下当前枚举的乐曲，有
f[j][k]=f[j][k-a[i]]+1。
上面三种情况取最大值。
答案显然是f[m][t]。
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=25;
int n,t,m,a[N],f[N][N];
signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n>>t>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){for(int j=m;j>=1;j--){for(int k=t;k>=a[i];k--){f[j][k]=max(f[j][k],max(f[j-1][t]+1,f[j][k-a[i]]+1));}}}cout<<f[m][t];return 0;
}
2. P1436 棋盘分割【部分存疑】
二维区间DP好题。
注意到变量的数据范围都特别小，所以可以定义上述矩形区间割t刀的最大贡献是f[i][j][k][l][t]。
对于t=0的情况，相当于一刀都没割，直接前缀和+自平方预处理即可，这里不多赘述。
状态转移相当于一个区间DP的思想：
对于竖着切的情况，断点是直线X=a，那么矩形(i,j)~(k,l)被分为(i,j)~(k,a)和(i,a+1)~(k,l)，对于这两部分，肯定有一个的第五维是t-1，另一个是0，则分两种情况讨论，取最大值即可。
对于横着切的情况同理，也取最大值。
上述两种情况再取最大值，得到f[i][j][k][l][t]的转移。
答案显然是f[1][1][8][8][n-1]。
存疑点：为什么t的遍历要写在坐标遍历的最外面？背包问题的遍历层级问题会对状态转移造成什么影响？
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=18,M=10;
int n,arr[M][M],sum[M][M],f[M][M][M][M][N];
signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n;for(int i=1;i<=8;i++){for(int j=1;j<=8;j++){cin>>arr[i][j];sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];}}for(int i=1;i<=8;i++){for(int j=1;j<=8;j++){for(int k=1;k<=8;k++){for(int l=1;l<=8;l++){f[i][j][k][l][0]+=sum[k][l]-sum[k][j-1]-sum[i-1][l]+sum[i-1][j-1];f[i][j][k][l][0]*=f[i][j][k][l][0];} } }}for(int t=1;t<n;t++){for(int i=1;i<=8;i++){for(int j=1;j<=8;j++){for(int k=1;k<=8;k++){for(int l=1;l<=8;l++){int minn=INT_MAX;for(int a=j;a<l;a++){minn=min(minn,min(f[i][j][k][a][t-1]+f[i][a+1][k][l][0],f[i][j][k][a][0]+f[i][a+1][k][l][t-1]));}for(int b=i;b<k;b++){minn=min(minn,min(f[i][j][b][l][t-1]+f[b+1][j][k][l][0],f[i][j][b][l][0]+f[b+1][j][k][l][t-1]));}f[i][j][k][l][t]=minn;}} } }}cout<<f[1][1][8][8][n-1];return 0;
}
)
