DP专题考试
这几天考了很多场DP啊，属实是考废了，中途因为唐氏错误保龄了一次，其他几次考的也不是很理想，可能跟最近低迷的状态有关吧。
现在开学停课搞竞赛，先把前几天的DP总结一下。
Day1（2024.8.30）
T1 天平（balance）
题意
有一个杠杆，有若干个秤砣，重量为 \(w_i\)，和若干个可以放置秤砣的位置 \(p_i\)，求在使用所有秤砣的条件下，有多少种挂秤砣的方案，可以使杠杆平衡（力矩之和为0）。
思路
我们考虑 \(dp_{i,j}\) 表示的是放了前 \(i\) 个秤砣，当前力矩为 \(j\) 的方案数。
对于当前秤砣 \(i\)，它放到第 \(j\) 个可以放的位置的力矩为 \(w_i \times p_j\)。
那么就能得到：
\[dp_{i,j}=dp_{i-1,j-w_i \times p_j}+dp_{i,j} \]再看一眼限制：
\(n,m \le 20\)
直接秒了（为什么时间如此充裕）。
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
template<typename P>
inline void read(P &x){
P res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
x=res*f;
}
template<typename PP>
inline void write(PP x){
if(x<0) putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar('0'+x%10);
}
int T=1;
int n,m;
int w[22],s[22],co[22][22];
unordered_map<int,int> dp[22];//前i个力举之和为j
signed main(){
auto solve=[&](){
read(n),read(m);
for(int i=1;i<=n;++i) read(s[i]);
for(int i=1;i<=m;++i) read(w[i]);
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
co[i][j]=s[j]*w[i];
}
}
dp[0][0]=1;
for(int i=1;i<=m;++i){
for(int j=-10000;j<=10000;++j){
for(int k=1;k<=n;++k){
dp[i][j]=dp[i-1][j-co[i][k]]+dp[i][j];
}
}
}
cout<<dp[m][0]<<endl;
};
freopen("balance.in","r",stdin);
freopen("balance.out","w",stdout);
// read(T);
while(T--) solve();
return 0;
}
T2 山峰数（hill）
题意
山峰数是指数字排列中不存在山谷(先降后升)的数，例如 0,5,13,12321 都是山峰数，101，1110000111 都不是山峰数。
现给出 n 个数，请依次判断它们是否为山峰数，如果不是，输出-1。如果是，求出比它小的数中有多少个山峰数。
思路
简单数位DP，因为要考虑之前是否下降过，所以在转移过程过添加一维 \(flag\) 表示之前是否已经下降过了，然后还需要一维前缀 \(pre\)。
填数字的时候只需要判断一下是否 \(flag\) 并且当前填的数比前缀 \(pre\) 大，如果是，则跳过，否则搜索。
如果当前是下降的，把 \(flag\) 设为 \(1\) 即可，其余情况不变。
其实数位DP用记忆化搜索好理解多了。
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
template<typename P>
inline void read(P &x){
P res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
x=res*f;
}
template<typename PP>
inline void write(PP x){
if(x<0) putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar('0'+x%10);
}
int T=1;
char a[72];
int n;
int num[72];
int f[72][72][2];
int dfs(int now,bool op0,bool lim,int pre,bool flag){
if(!now) return 1;
if(!op0 && !lim && f[now][pre][flag]!=-1) return f[now][pre][flag];
int up=lim?num[now]:9,res=0;
for(int i=0;i<=up;++i){
if(flag && i<=pre) res+=dfs(now-1,(op0 && i==0),(lim && i==up),i,1);
else if(!flag) res+=dfs(now-1,(op0 && i==0),(lim && i==up),i,(i<pre));
}
if(!op0 && !lim) f[now][pre][flag]=res;
return res;
}
signed main(){
memset(f,-1,sizeof(f));
auto solve=[&](){
cin>>(a+1);
n=strlen(a+1);
bool down=0;
for(int i=1;i<=n;++i) num[i]=a[i]-'0';
for(int i=1;i<n;++i){
if(num[i]<num[i+1] && down){
cout<<-1<<endl;
return;
}
if(num[i]>num[i+1]) down=1;
}
reverse(num+1,num+n+1);
cout<<dfs(n,1,1,0,0)-1<<endl;
};
freopen("hill.in","r",stdin);
freopen("hill.out","w",stdout);
read(T);
while(T--) solve();
return 0;
}
T3 粉刷匠 2（draw）
题意
\(4 \times n\) 的矩阵，有 256 种颜色，每个位置都可以选择一种颜色。
现在要满足以下条件：
- \(A(x,y) \ge A(x,y-1)\)
- 有一些指定的 \((x1,y1)\) 和 \((x2,y2)\)，要求 \(A(x1,y1)=A(x2,y2)\)
求方案数，只输出答案后 5 位。
思路
比较有意思的背包。
我们不按照常规思维枚举行列，而是从小到大枚举颜色。若当前枚举到的颜色为 \(i\)，我们使用 \(dp[l1][l2][l3][l4]\) 表示每一行使用当前颜色涂到哪一个位置。
假设有一行现在是 123344556，现在涂 7，显然涂 7 只能涂序列的后缀，比如涂成 123777777，或者 123344577 才能符合条件。所以考虑枚举当前颜色涂到哪个后缀来转移，转移时同样需要使用完全背包的降维思想优化。
对于限制条件，我们需要把不符合限制条件的去掉，什么样的方案符合限制条件呢？对于限制条件 \(A(x1,y1) = A(x2,y2)\)，和当前枚举到的颜色 \(i\)，要么 \(x1\) 行和 \(x2\) 行，当前颜色都涂到了 \(y1,y2\) 位置，要么都没有涂到 \(y1,\) 位置。除此之外的都是不合法的方案，我们事先处理好一个 \(vis\) 数组，\(vis[l1][l2][l3][l4]\) 表示四行分别涂到 \(l1,l2,l3,l4\)，是否可行，在 dp 时如果遇到标记不可行的 \(vis\)，这 dp 值设为 \(0\) 即可。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
template<typename P>
inline void read(P &x){
P res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
x=res*f;
}
template<typename PP>
inline void write(PP x){
if(x<0) putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar('0'+x%10);
}
int T=1;
const int mod=100000;
int n,m,tc=1;
int c[4];
int f[16][16][16][16];
bool vis[16][16][16][16];
int r1x[105],r2x[105],r1y[105],r2y[105];
signed main(){
auto solve=[&](){
for(int tt=1;tt<=tc;++tt){
memset(vis,0,sizeof(vis));
read(n),read(m);
for(int i=1;i<=m;++i){
read(r1x[i]),read(r1y[i]),read(r2x[i]),read(r2y[i]);
r1x[i]--,r2x[i]--;
}
for(int i=1;i<=m;++i){
for(c[0]=0;c[0]<=n;++c[0])
for(c[1]=0;c[1]<=n;++c[1])
for(c[2]=0;c[2]<=n;++c[2])
for(c[3]=0;c[3]<=n;++c[3])
if(c[r1x[i]]>=r1y[i]^c[r2x[i]]>=r2y[i])
vis[c[0]][c[1]][c[2]][c[3]]=1;
}
memset(f,0,sizeof(f));
f[0][0][0][0]=1;
for(int col=0;col<=255;++col){
for(int cc=0;cc<=3;++cc)
for(c[0]=0;c[0]<=n;++c[0])
for(c[1]=0;c[1]<=n;++c[1])
for(c[2]=0;c[2]<=n;++c[2])
for(c[3]=0;c[3]<=n;++c[3])
if(c[cc]<n){
int tmp=f[c[0]][c[1]][c[2]][c[3]];
c[cc]++;
f[c[0]][c[1]][c[2]][c[3]]=(f[c[0]][c[1]][c[2]][c[3]]+tmp)%mod;
c[cc]--;
}
for(c[0]=0;c[0]<=n;++c[0])
for(c[1]=0;c[1]<=n;++c[1])
for(c[2]=0;c[2]<=n;++c[2])
for(c[3]=0;c[3]<=n;++c[3])
if(vis[c[0]][c[1]][c[2]][c[3]]) f[c[0]][c[1]][c[2]][c[3]]=0;
}
printf("%05d\n",f[n][n][n][n]);
}
};
// freopen("draw.in","r",stdin);
// freopen("draw.out","w",stdout);
//read(T);
while(T--) solve();
return 0;
}
T4 棋盘（knight）
题意
有一个 \(N \times M\) 的棋盘，要在上面摆上 knight，每个格子可以放至多一个knight。
knight 的攻击范围为国际象棋中马的移动范围。
所有 knight 不能互相攻击，请问总共有多少可行的摆法？答案对 1000000007 取模。
思路
状压DP
考虑压当前行，上一行，上两行三个状态。
转移还是正常转移，但是这样你会发现你寄了。
这个时候我们发现可以使用矩阵优化。
不会写。
以后考试总结都放在这里吧，现在就不补了。
标签：总结,10,ch,int,long,dp,考试,define From： https://www.cnblogs.com/lizihan00787/p/18404773