总结
DP之所以难，主要在于其不固定，每一个转移方程的推导方式与转移方式都不一样，需要结合具体的题目来看
E - Count Arithmetic Subsequences
地址
题目要求等差数列的个数，我们知道确定一个等差数列需要首项、公差、项数，在本题中还多了一个量————位置
因为询问了不同长度的等差数列的个数，因此必须要项数这一维
同时本题数量较少而值域较大，并且因为不同下标的相同等差数列视为不同
考虑从下标入手，等差数列的第一项、第二项以及项数同样可以确定一个等差数列
具体到转移，一个长度为$i$的等差数列一定是从长度为$i-1$的等差数列转移而来,因此在转移时枚举前面公差相同的等差数列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| void SINGLE_TEST()
{
int n;cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
// 第二项为i，第一项为j，项数为k的等差数列的个数
vector<vector<vector<Z>>> dp(N+1,vector<vector<Z>>(N+1,vector<Z>(N+1,0)));
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
dp[i][j][2]+=1;
for(int q=1;q<j;q++){
for(int k=3;k<=i;k++){
if(a[i]-a[j]==a[j]-a[q])
dp[i][j][k]+=dp[j][q][k-1];
}
}
}
}
vector<Z> ans(n+1);
ans[1]=n;
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
for(int k=2;k<=i;k++){
ans[k]+=dp[i][j][k];
}
}
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<" \n"[i==n];
}
}
|
E - Alphabet Tiles
地址
这是一种前i个所能达成的答案的题型，比较经典，但是如果没有想到这方面可能就比较难设计出正确的dp状态
在此基础上，本题我们考虑$dp[i][j]$为前$j$个字母、长度为$i$的方案数
对于递推关系，考虑推到前$j$个字母、长度为$i$的情形，从前$j-1$个字母、长度为$s(s \leqslant i)$的情形递推，第$j$个字母，可以在已有的字符串中随意插入，插的数量则是$i-s$，方案数即为$C_{i}^{i-s}$,可以这样想，$i$个位置先什么都不放，把那些差值个数的字母插入后再放入原先的字母
代码中枚举的是差值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void SINGLE_TEST()
{
int k;cin>>k;
vector<int> cnt(27);
for(int i=1;i<=26;i++){
cin>>cnt[i];
}
// 前c个字母，组成长度为i的字符串的方案数
vector<vector<Z>> dp(k+1,vector<Z>(26+1,0));
for(int i=0;i<=26;i++) dp[0][i]=1;
for(int c=1;c<=26;c++){
for(int i=1;i<=k;i++){
for(int j=0;j<=min(i,cnt[c]);j++){
dp[i][c]+=dp[i-j][c-1]*C(i,j);
}
}
}
Z ans=0;
for(int i=1;i<=k;i++){
ans+=dp[i][26];
}
cout<<ans<<"\n";
}
|