9月1-5日小记 - L

9月1日

1. P1616 疯狂的采药

这显然是完全背包，但我们提出一种不同的理解。

完全背包之所以正序遍历，是因为每一个物品都可以无限取。

反观0-1背包，所遍历容量j的决策值dp[j]在转移过程中需要用到dp[j-a[i]]的值。显然j-a[i]严格小于j，所以在遍历时，dp[j-a[i]]的值在dp[j] 后更新，转移dp[j]时还没有更新。至于完全背包，dp[j-a[i]]的值在dp[j] 前更新。

考虑一个完全背包的非滚动数组转移方程：

\[f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i]) \]

而0-1背包的非滚动数组转移方程：

\[f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]) \]

注意到max函数的第二项不同。所以，完全背包转移时，依赖当前行的前驱状态；0-1背包转移时，依赖上一行的前驱状态。而且，不管哪种背包，转移时不是依赖当前行的前驱状态，就是依赖上一行的前驱状态。这一思想极其重要。

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=1e4+5,M=1e7+5;
int t,m,a[N],b[N],f[M];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t>>m;for(int i=1;i<=m;i++){cin>>a[i]>>b[i];}for(int i=1;i<=m;i++){for(int j=a[i];j<=t;j++){f[j]=max(f[j],f[j-a[i]]+b[i]);}}cout<<f[t];return 0;
}

2. P1450 [HAOI2008] 硬币购物

预备知识：容斥原理。

狭义的容斥原理一般用于计算多个集合的并的元素个数。推广而来，广义的容斥原理则用于计算满足多种性质的总元素个数。（可能表述的不太清）也可以把一个集合内的所有元素看作所有满足某个性质的元素。

容斥原理的一般形式是：

\[\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right| \]

举例：当\(n=3\)时，有：

\[∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C| \]

其中\(|A|\)表示集合\(A\)的元素个数。

这题可以先处理完全背包，然后用凑出金额s的不加限制的总方案数减去不合法的方案数。这就涉及到容斥原理。

定义f[j]。显然f[j]可以从所有的f[j-c[i]]转移而来，并累加求和，相当于f*1的乘法原理。

所以如果第i种硬币使用超限，那么一定用了大于等于(d[i]+1)个i种硬币，相当于状态从f[j-c[i]*(d[i]+1)]转移而来。

超限时，硬币数大于d[i]+1的情况则一定会被包含在f[j-c[i]*(d[i]+1)]里，所以我们只需要考虑f[j-c[i]*(d[i]+1)]即可。

但是我们想到，同时计算四种金币的不合法方案数可能会有算重的情况，于是我们考虑容斥原理（可以画Venn图来形象理解）：不加限制的总方案数 - (一种金币超限的方案数 - 两种金币超限的方案数 + 三种金币超限的方案数 - 四种金币超限的方案数) = 答案（即奇加偶减）。

后面括号里的运算结果就是所有不合法的方案总数。

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int M=1e5+10;
int c[5],d[5],f[M],n,s,ans;
int judge(int x){int cnt=0;while(x){cnt++;x-=x&(-x);}return (cnt%2==1)?-1:1;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);for(int i=1;i<=4;i++){cin>>c[i];}cin>>n;f[0]=1;for(int i=1;i<=4;i++){for(int j=c[i];j<=M-10;j++){f[j]+=f[j-c[i]];}}while(n--){ans=0;for(int i=1;i<=4;i++){cin>>d[i];}cin>>s;for(int i=0;i<16;i++){//枚举二进制状态//使用四位二进制数来表示目前考虑第几个集合的交int sum=0;for(int j=0;j<4;j++){//枚举状态i的每一位if(i & (1<<j)){sum+=c[j+1]*(d[j+1]+1);}}if(s-sum>=0)ans+=judge(i)*f[s-sum];}cout<<ans<<endl;}return 0;
}

9月2日

1. P2167 [SDOI2009] Bill的挑战

状压预处理+状压DP。好题。

首先观察数据范围，注意到N<=15，所以考虑压缩N及其相关量。

我们在枚举串T的每一位时，对于每一位的元素，这一元素对于所给出的n个字符串s[]在它所在的位置，只有能匹配或不能匹配两种选择，正好对应二进制中的两种状态。

例如，N=3，len=4（即字符串长度），下面这组数据：

	? c ? b ? ?a ? ? ? ? ?? d ? ? e ?
T:	_ _ _ _ _ _

假如现在枚举到串T的第二个元素，如果这一位填入字母d，那么对于s[1]，它不匹配；对于s[2]，它匹配；对于s[3]，它匹配。

所以，我们可以开一个数组g[i][c]，它表示：串T的第i个位置填入字母c-'a'，对于所有给定的串s的匹配状态。比方说上面的例子，g[2]['d'-'a']=011。

显然，g数组可以预处理。下面开始转移。

考虑到串T的枚举位数和匹配状态都会影响目标答案，所以将它们融入状态定义：定义f[i][st]表示串T枚举到第i位，串T的匹配状态为st，此时串T可能的总情况数。

似乎不太好转移。这是一道求方案数的DP。让我们想想另一道求方案数的DP题：完全背包求方案数。

这个问题的转移方程为f[j]+=f[j-v[i]]。价值j显然大于价值(j-v[i])，即前者是后者的后继状态。所以我们发现，后继状态总由前驱状态转移而来（即动态规划问题的无后效性）。这个状态转移方程还能写成f[j+v[i]]+=f[j]。

类比本题，比方说现在枚举到串T的第i位，则这一位的状态必由第(i-1)位的状态转移而来。所以我们考虑状态f[i-1][j]被包含在了哪种状态里，即由被哪种状态转移。

不难想到f[i][j&g[i][k]]包含f[i-1][j]。因为在枚举字母k时，它的匹配状态g[i][k]必须和上一步的状态j按位与，才能得到现在的状态。即状态转移方程是f[i][j&g[i][k]]+=f[i-1][j]。

答案统计：所有二进制1的个数等于k的，长度等于字符串长度的f数组值的和。记得取模。

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1000003;
int q,n,len,tlen,ans,g[55][30],f[55][1<<15];
string s[18];
int getcnt(int x){int cnt=0;while(x){cnt++;x-=x&(-x);}return cnt;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>q;while(q--){memset(f,0,sizeof(f));memset(g,0,sizeof(g));cin>>n>>tlen;for(int i=1;i<=n;i++){cin>>s[i];s[i]=' '+s[i];}len=s[1].length()-1;for(int i=1;i<=len;i++){//位数for(int j=0;j<26;j++){//字母for(int k=1;k<=n;k++){//行数if(s[k][i]=='?' || s[k][i]==(j+'a')){g[i][j] |= (1<<(k-1));}}}}f[0][(1<<n)-1]=1;for(int i=1;i<=len;i++){for(int j=0;j<(1<<n);j++){if(f[i-1][j]==0)continue;for(int k=0;k<26;k++){f[i][j&g[i][k]]=(f[i][j&g[i][k]]+f[i-1][j])%mod;}}}ans=0;for(int j=0;j<(1<<n);j++){if(getcnt(j)==tlen){ans=(ans+f[len][j])%mod;}}cout<<ans<<endl;}return 0;
}

2. P3800 Power收集

线性DP+单调队列优化。

状态定义不说了，状态转移方程也显然是f[i][j]=max(f[i-1][k])+a[i][j]，其中j-t<=k<=j+t。

如果分别枚举i、j、k，时间复杂度会变为三次方级的，故考虑优化。

注意到我们在遍历每个j的时候，都会产生一个固定长度2t+1的窗口，且这个窗口的中心点是j。

也就是说，我们可以使用滑动窗口维护该窗口的最值，但是这个窗口是中心对称的，所以我们不太好用一遍的队列操作直接得到f[i-1][k]的最大值。

我们考虑操作两遍：从左转移来的、从右转移来的。

对于每一遍操作，相当于维护一个长度折半的滑动窗口，易于编码。

修改：对于每次操作的状态转移，不需要加任何判断条件。

如果加了判断条件（窗口是否成型），那么当窗口未成形时，将不会进行任何状态转移，经过计算的状态会少一些，会干扰以后的计算。

而不加判断条件的话，单调队列的队头也会不断返回使f[i-1][k]最大的k，当然可以用于状态转移。所以不需要加判断条件。

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=4010;
int n,m,k,t,a[N][N],f[N][N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>k>>t;while(k--){int x,y,v;cin>>x>>y>>v;a[x][y]=v;}for(int j=1;j<=m;j++){f[1][j]=a[1][j];}for(int i=2;i<=n;i++){deque<int>dq;//从左转移来的for(int j=1;j<=m;j++){while(!dq.empty()&&f[i-1][dq.back()]<=f[i-1][j]){dq.pop_back();}while(!dq.empty()&&dq.front()<j-t){dq.pop_front();}dq.push_back(j);f[i][j]=f[i-1][dq.front()]+a[i][j];}dq.clear();//从右转移来的for(int j=m;j>=1;j--){while(!dq.empty()&&f[i-1][dq.back()]<=f[i-1][j]){dq.pop_back();}while(!dq.empty()&&dq.front()>j+t){dq.pop_front();}dq.push_back(j);f[i][j]=max(f[i][j],f[i-1][dq.front()]+a[i][j]);}}int ans=0;for(int j=1;j<=m;j++){ans=max(ans,f[n][j]);}cout<<ans;return 0;
}

9月3日

1. P3572 [POI 2014] PTA-Little Bird

线性DP+单调队列优化。

定义f[i]表示走到第i格所需的最小劳累值，可以考虑纯线性DP的写法：f[i]=f[i-p]+(a[i]>=a[i-p])，其中1<=p<=k。

注意到这样枚举i和p的时间复杂度达到二次方形式，故考虑优化。

显然，k是个定值（滑动窗口所维护的区间一般需定长），那么就可以想象：对于所枚举的每个i，都有一个长度为k的严格单调递减的滑动窗口在后面跟着，用于维护长度为定长的区间内，最小的f[i-p]。

需要特判的是，如果f[dq.back()]（也就是目前认为最小的f[i-p]）恰好与f[i]相等，那么需要进一步比较。

考虑一个贪心：再次维护这个队列，使得队列内的a[i-p]始终单调递增，进而使得队首的a[i-p]始终最大，使(a[i]>=a[i-p])尽可能为假。

注意滑动窗口代码模板实现的顺序：

1. 移除过期元素
2. 转移
3. 维护队列单调性
4. 入栈

这个顺序可以保证转移时所使用的队首元素始终不过期。不同滑动窗口题目中，代码模板的实现顺序也可能不同。（待议）

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=1e6+10;
int n,a[N],q,k,f[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}cin>>q;while(q--){deque<int>dq;memset(f,0,sizeof(f));dq.push_back(1);cin>>k;for(int i=2;i<=n;i++){while(!dq.empty()&&dq.front()<i-k){dq.pop_front();}f[i]=f[dq.front()]+(a[i]>=a[dq.front()]);while(!dq.empty()&&((f[dq.back()]>f[i]) || (f[dq.back()]==f[i] && a[dq.back()]<=a[i]))){dq.pop_back();}dq.push_back(i);}cout<<f[n]<<endl;}return 0;
}

2. P7567 「MCOI-05」魔仙

神秘构造，待补全。

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
signed main(){scanf("%d",&T);while(T--){scanf("%d",&n);if(n%4==0){int k=n/4;if(k%2){printf("2 -%d ",k*2);for(int i=1;i<=3*k-2;i++){printf("1 ");}for(int i=1;i<=k;i++){printf("-1 ");}}else{printf("-2 -%d ",k*2);for(int i=1;i<=3*k;i++){printf("1 ");}for(int i=1;i<=k-2;i++){printf("-1 ");}}printf("\n");}else{printf("w33zAKIOI\n");}}return 0;
}

3. P6394 樱花，还有你

线性DP+前缀和优化。

设f[i][j]表示走到第i格，恰好收集到j朵樱花的方案数。

显然f[i][j]+=f[i-1][j-k]，其中1<=k<=a[i]。

注意到两个事情：

1. i在转移过程中没用，可以滚掉；
2. 所累加的f[j-k]中的k是连续的，所以累加的值也是连续的，可以用前缀和优化。

开一个前缀和数组s[j]表示f[1]到f[j]的和。

状态转移方程显然为f[j]=s[j]-s[j-a[i]-1]，当且仅当j>a[i]；如果不，则f[j]=s[j]。

每次循环枚举i的时候，都要将f[n]累加到ans中，并重新预处理前缀和数组。

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=5e3+10,mod=10086001;
int n,k,a[N],f[N],s[N],tot,ans;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;for(int i=1;i<=k;i++){cin>>a[i];tot+=a[i];}if(tot<n){cout<<"impossible";return 0;}f[0]=s[0]=1;for(int i=1;i<=k;i++){s[0]=f[0];for(int j=1;j<=n;j++){s[j]=(s[j-1]+f[j])%mod;}for(int j=0;j<=n;j++){if(j>a[i]){f[j]=(s[j]-s[j-a[i]-1])%mod;}else{f[j]=s[j];}}ans=(ans+f[n])%mod;}cout<<(ans+mod)%mod;return 0;
}

4. P11248 [GESP202409 七级] 矩阵移动

这题显然不是橙。

三维DP。形象地说，二维的矩阵影响决策，一维的操作数也影响决策。

定义f[i][j][k]表示当前走到点(i,j)，已修改k个'?'的最大分数。

显然，不管a[i][j]上的元素是什么，都有：f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k])+(a[i][j]=='1')；

特别地，如果a[i][j]上的元素是'?'，且目前所枚举的k>0，则：f[i][j][k]=max(f[i][j][k],max(f[i-1][j][k-1],f[i][j-1][k-1])+1)。

答案为f[n][m][k]的最大值。

提交，MLE所有点，考虑滚动数组优化。

注意到每一行的所有状态均由这一行和这一行的前一行转移而来，所以可以考虑滚掉第一维。

将所有的i-1换为(i+1)&1，将所有的i换为i&1即可。这里利用了本文最开始介绍的思想。(i+1)&1表示从上一行转移而来，i&1则表示从这一行转移而来。

最后答案即为f[n&1][m][k]的最大值。

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=505,M=305;
int q,n,m,t,ans,f[2][N][M];
char a;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>q;while(q--){memset(f,0,sizeof(f));cin>>n>>m>>t;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a;for(int k=0;k<=t;k++){f[i&1][j][k]=max(f[(i+1)&1][j][k],f[i&1][j-1][k])+(a=='1');if(a=='?' && k>0){f[i&1][j][k]=max(f[i&1][j][k],max(f[(i+1)&1][j][k-1],f[i&1][j-1][k-1])+1);}}}}ans=0;for(int k=0;k<=t;k++){ans=max(ans,f[n&1][m][k]);}cout<<ans<<endl;}return 0;
}