简单dp指的是不需要较高难度算法的dp
选取 Codeforces 难度 2100-2500 的 dp 题 进行训练
虽然很多题实际都不怎么像 dp 但是总之做一做没啥坏处(雾
简洁起见把快读去掉了()
1428F Fruit Sequences
link(*2400)
考虑常规的枚举右端点统计答案的思路
我们称一个极长的全 1 子串为一个连通块
维护一个 数组, 表示最后一个 ,距离 所在连通块的最后一个位置 长度为 (即 )
每次统计答案的时候分类:如果当前枚举的右端点(称为 ) 则没有什么贡献,更新一下
如果 则要加上以 为右端点的整个连通块产生的贡献
若上一句提到的这个连通块的长度为 ,则产生的贡献为 。
复杂度
// 2020.11.13
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=500005;
int n;
bool a[MAXN];
int dp[MAXN];
int ans=0;
signed main()
{
n=read();
for (int i=1;i<=n;i++)
a[i]=readch()=='1';
int len=0,tmp=0;
for (int i=1;i<=n;i++){
if (a[i]) tmp+=i-dp[++len];
else{
while (len) dp[len]=i-len,len--;
}
ans+=tmp;
}
cout<<ans<<endl;
return 0;
}
771D Bear and Company
link(*2500)
看到ycx的题解就去做了一下(
设 为当前移了 个 V
, 个 P
, 个其他字母到前 (设 )个位置的最小操作次数, 记录最后一位是否为 V
。
随便转移一下就好了
复杂度
// 2020.11.12
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int MAXN=100;
int n;
vector<int> V={0},K={0},X={0};
int dp[MAXN][MAXN][MAXN][3];
inline int calc(int x,int y,int z,int pos){
int ans=pos-(x+y+z+1);
for (int i=1;i<=x;i++) if (V[i]>=pos) ans++;
for (int i=1;i<=y;i++) if (K[i]>=pos) ans++;
for (int i=1;i<=z;i++) if (X[i]>=pos) ans++;
// cout<<x<<' '<<y<<' '<<z<<' '<<pos<<' '<<ans<<endl;
return ans;
}
signed main()
{
memset(dp,0x3f3f3f3f,sizeof(dp));
n=read();
for (int i=1;i<=n;i++){
char tmp=readch();
if (tmp=='V') V.push_back(i);
else if (tmp=='K') K.push_back(i);
else X.push_back(i);
}
dp[0][0][0][0]=dp[0][0][0][1]=0;
for (int i=0;i<V.size();i++){
for (int j=0;j<K.size();j++){
for (int k=0;k<X.size();k++){
if (i!=0) dp[i][j][k][1]=min(dp[i][j][k][1],min(dp[i-1][j][k][0],dp[i-1][j][k][1])+calc(i-1,j,k,V[i]));
if (k!=0) dp[i][j][k][0]=min(dp[i][j][k][0],min(dp[i][j][k-1][0],dp[i][j][k-1][1])+calc(i,j,k-1,X[k]));
if (j!=0) dp[i][j][k][0]=min(dp[i][j][k][0],dp[i][j-1][k][0]+calc(i,j-1,k,K[j]));
}
}
}
cout<<min(dp[V.size()-1][K.size()-1][X.size()-1][0],dp[V.size()-1][K.size()-1][X.size()-1][1])<<endl;
return 0;
}
1420E Battle Lemmings
link(*2500)
设 为考虑到第 个位置且第 个位置为 ,已经进行了 次操作,前 个数中有 个为 1 的最大答案
每次转移枚举下一个填 1 的位置进行更新
时间复杂度 ,看起来完全不可能过但是实际跑得飞快
细节很多,调了一年
// 2020.11.14
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int MAXN=85;
int n;
bool a[MAXN];
vector<int> v;
int dp[MAXN][MAXN*MAXN/2][MAXN];
// dp[i][j][k] 表示前i个,j次操作,k个1
int mx[MAXN][MAXN];
inline int calc(int i,int j,int k,int l){
return (i-k)*(l-i-1);
}
signed main()
{
memset(dp,-1,sizeof(dp));
n=read();
int N=n*(n-1)/2;
for (int i=1;i<=n;i++){
a[i]=read();
if (a[i]) v.push_back(i);
}
dp[0][0][0]=0;
for (int i=0;i<n;i++){
for (int j=0;j<N;j++){
for (int k=min(i,1);k<=min(i,int(v.size()-1));k++){
// if (j!=0) dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k]);
if (dp[i][j][k]==-1) continue;
for (int qwq=i+1;qwq<=n;qwq++){
int dis=abs(v[k]-qwq);
if (j+dis>N) continue;
dp[qwq][j+dis][k+1]=max(dp[qwq][j+dis][k+1],dp[i][j][k]+calc(i,j,k,qwq));
// printf("dp[%d][%d][%d]=%d\t -> \t dp[%d][%d][%d]=%d\n",i,j,k,dp[i][j][k] ,qwq,j+dis,k+1,dp[qwq][j+dis][k+1]);
}
}
}
}
int ans=0;
for (int j=0;j<=N;j++){
int k=v.size();
for (int i=k;i<=n;i++){
if (dp[i][j][k]!=-1) ans=max(ans,dp[i][j][k]+max(0,(n-i)*(i-k)));
}
cout<<ans<<' ';
}
cout<<endl;
return 0;
}
1409F Subsequences of Length Two
link(*2100)
记 为 , 为
设 为考虑到第 个位置,用了 次操作, 前面有 个 的答案
随便转移
需要特判一下 的情况
时间复杂度
// 2020.11.14
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int MAXN=205;
int n,k;
int a[MAXN];
int dp[MAXN][MAXN][MAXN];
int ans=0;
signed main()
{
n=read();k=read();
string s=readstr(),t=readstr();
for (int i=1;i<=n;i++){
if (s[i-1]==t[0]) a[i]=0;
else if (s[i-1]==t[1]) a[i]=1;
else a[i]=-1;
}
if (t[0]==t[1]){
ans=k;
for (int i=1;i<=n;i++)
ans+=a[i]==0;
ans=min(ans,n);
ans=ans*(ans-1)/2;
cout<<ans<<endl;
return 0;
}
memset(dp,-0x3f3f3f3f,sizeof(dp));
for (int i=0;i<=n;i++)
dp[i][0][0]=0;
for (int i=1;i<=n;i++){
for (int j=0;j<=k;j++){
for (int x=0;x<=i;x++){
dp[i][j][x]=max(dp[i][j][x],dp[i-1][j][x]);
if (a[i]==0 && x!=0) dp[i][j][x]=max(dp[i][j][x],dp[i-1][j][x-1]);
if (a[i]==1) dp[i][j][x]=max(dp[i][j][x],dp[i-1][j][x]+x);
if (j!=0 && x!=0){
dp[i][j][x]=max(dp[i][j][x],dp[i-1][j-1][x-1]);
dp[i][j][x]=max(dp[i][j][x],dp[i-1][j-1][x]+x);
}
}
}
}
for (int j=0;j<=k;j++){
for (int x=0;x<=n;x++)
ans=max(ans,dp[n][j][x]);
}
cout<<ans<<endl;
return 0;
}
1348E Phoenix and Berries
link(*2400)
首先考虑一个显然的朴素 :设 表示到第 棵树,多出 个红梅和 个蓝莓的答案。
这样的话状态数 ,转移 ,总复杂度为 ,无法通过。
注意到对于每个位置, 在 意义下是恒定不变的,优化一下就可以做到状态数 ,转移 ,总复杂度 的 了。
是个卡常题,加了火车头,把 优化掉了之后才能过
但是洛谷不允许 #pragma
,所以洛谷提交死活过不了 = =
// 2020.11.21
// Code by LTb
/*省略火车头*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=505;
int n,k;
int a[MAXN],b[MAXN];
int dp[MAXN][MAXN];
int sum[MAXN];
int sum1[MAXN],sum2[MAXN];
int qaq[MAXN],qaq1[MAXN],qaq2[MAXN];
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline int qwq(int x){return (x>=k)?(x-k):x;}
signed main()
{
n=read();k=read();
for (int i=1;i<=n;i++){
a[i]=read();b[i]=read();
sum[i]=sum[i-1]+a[i]+b[i];
sum1[i]=sum1[i-1]+a[i];
sum2[i]=sum2[i-1]+b[i];
qaq[i]=sum[i]%k;
qaq1[i]=sum1[i]%k;
qaq2[i]=sum2[i]%k;
}
for (int i=1;i<=n;i++){
int tmp1=min(sum1[i]+1,k),tmp2=min(sum1[i-1]+1,k);
for (int j=0;j<tmp1;j++){
int l=qwq(qaq[i]+k-j);
if (l>sum2[i]) continue;
for (int x=0;x<tmp2;x++){
int y=qwq(qaq[i-1]+k-x);
int cnt1=qwq(j-x+k),cnt2=qwq(l-y+k);
if (cnt1>a[i] || cnt2>b[i] || y>sum2[i-1]) continue;
dp[i][j]=max(dp[i][j],dp[i-1][x]+(j<x)+(l<y)+(a[i]+b[i]-cnt1-cnt2)/k);
}
}
}
int ans=0;
for (int i=0;i<=k;i++)
ans=max(ans,dp[n][i]);
printf("%lld\n",ans);
return 0;
}
1336C Kaavi and Magic Spell
link(*2200)
设 表示用 的前 个字符填满 的方案数
记得答案要
// 2020.11.22
// Code by LTb
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=3005;
const int MOD=998244353;
int n,m;
char a[MAXN],b[MAXN];
int dp[MAXN][MAXN];
signed main()
{
string s1=readstr(),s2=readstr();
n=s1.size();m=s2.size();
for (int i=1;i<=n;i++)
a[i]=s1[i-1];
for (int i=1;i<=m;i++)
b[i]=s2[i-1];
for (int i=1;i<=n;i++)
dp[i][i]=(i>m) || (a[1]==b[i]);
for (int len=2;len<=n;len++){
for (int i=1;i+len-1<=n;i++){
int j=i+len-1;
dp[i][j]+=dp[i+1][j]*(a[len]==b[i] || i>m)+dp[i][j-1]*(a[len]==b[j] || j>m);
dp[i][j]%=MOD;
}
}
int ans=0;
for (int i=m;i<=n;i++)
ans=(ans+dp[1][i])%MOD;
cout<<(ans*2)%MOD<<endl;
return 0;
}
1332F Independent Set
1131E String Multiplication
link(*2300)
设 表示 到第 个字符串,最长的由字母 组成的子段长度。
预处理 (代码实现中为 数组)表示第 个字符串首 / 尾由字母 组成的字段长度。
随便转移
说句闲话:在这题里面第一次使用了
// 2020.11.28
// Code by LTb
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
inline void chmax(int &x,int y) {x=max(x,y);}
const int MAXN=100005;
int n;
string a[MAXN];
int siz[MAXN];
int youl[MAXN][30][2];
int dp[MAXN][30];
int ans=1;
signed main()
{
n=read();
for (int i=1;i<=n;i++){
a[i]="N"+readstr();
siz[i]=a[i].size()-1;
}
for (int j=1;j<=n;j++){
for (int i=1;i<=26;i++){
char now=i+'a'-1;
while (youl[j][i][0]<siz[j] && a[j][youl[j][i][0]+1]==now) youl[j][i][0]++;
while (youl[j][i][1]<siz[j] && a[j][siz[j]-youl[j][i][1]]==now) youl[j][i][1]++;
}
}
for (int i=1;i<=siz[1];i++){
int cur=i;
while (cur<siz[1] && a[1][cur+1]==a[1][cur]) cur++;
chmax(dp[1][a[1][i]-'a'+1],cur-i+1);
i=cur;
}
for (int i=2;i<=n;i++){
for (int j=1;j<=siz[i];j++){
int cur=j;
while (cur<siz[i] && a[i][cur+1]==a[i][cur]) cur++;
chmax(dp[i][a[i][j]-'a'+1],cur-j+1);
j=cur;
}
for (int j=1;j<=26;j++){
chmax(dp[i][j],max(youl[i][j][0],youl[i][j][1]));
if (dp[i-1][j]){
chmax(dp[i][j],1+youl[i][j][1]+youl[i][j][0]);
if (youl[i][j][0]==siz[i])
chmax(dp[i][j],dp[i-1][j]+(dp[i-1][j]+1)*siz[i]);
}
}
}
for (int i=1;i<=26;i++)
chmax(ans,dp[n][i]);
cout<<ans<<endl;
return 0;
}
1144G Two Merged Sequences
link(*2400)
设 。
表示 在递减序列中,递增序列末尾元素的最小值
表示 在递增序列中,递减序列末尾元素的最大值
随便转移
发现了有趣的事情: 是关键字
// 2020.12.11
// Code by LTb
#include <bits/stdc++.h>
using namespace std;
const int MAXN=200005;
const int INF=0x3f3f3f3f;
int n;
int a[MAXN];
int dp[2][MAXN];
// dp[0][i] 表示当前位置在递减序列中,递增序列的最小值
int refr[2][MAXN];
bool ans[MAXN];
signed main()
{
n=read();
for (int i=1;i<=n;i++)
a[i]=read();
for (int i=1;i<=n;i++)
dp[1][i]=-INF,dp[0][i]=INF;
dp[0][1]=-INF,dp[1][1]=INF;
for (int i=2;i<=n;i++){
if (a[i-1]>a[i] && dp[0][i-1]<dp[0][i]) {dp[0][i]=dp[0][i-1];refr[0][i]=0;}
if (a[i-1]<a[i] && dp[1][i-1]>dp[1][i]) {dp[1][i]=dp[1][i-1];refr[1][i]=1;}
if (dp[1][i-1]>a[i] && a[i-1]<dp[0][i]) {dp[0][i]=a[i-1];refr[0][i]=1;}
if (dp[0][i-1]<a[i] && a[i-1]>dp[1][i]) {dp[1][i]=a[i-1];refr[1][i]=0;}
}
if (dp[0][n]==INF && dp[1][n]==-INF){
puts("NO");
return 0;
}
puts("YES");
int cur=0;
if (dp[0][n]==INF) cur=1;
for (int i=n;i>=1;i--){
ans[i]=!cur;
cur=refr[cur][i];
}
for (int i=1;i<=n;i++)
cout<<ans[i]<<' ';
cout<<endl;
return 0;
}
1174E Ehab and the Expected GCD Problem
link(*2500)
是正睿暑假讲过的题(
注意到这个 必然是 中质因数个数最多的数 的质因数个数
显然这个数一定可以是形如 这样子的
实际上在某些情况下,这个数也可以是 ,但是其他数是不可能的,因为 ,。
设计一个 dp: ( ) 表示当前 dp 到第 个数,前缀 中有 个质因子 , 个质因子 的方案数。
转移的时候从 转移到 ,分几个类讨论:
- 不变
- 除以
- 除以
注意空间问题
// 2020.12.20
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
const int MOD=1e9+7;
int n;
int dp[MAXN][22][2];
inline int val(int x,int y){
return (1<<x)*((y==1)?3:1);
}
signed main()
{
n=read();
int lim=log2(n);
dp[1][lim][0]=1;
if ((1<<(lim-1))*3<=n) dp[1][lim-1][1]=1;
for (int i=2;i<=n;i++){
for (int j=0;j<=lim;j++){
for (int k=0;k<=1;k++){
dp[i][j][k]+=1ll*dp[i-1][j][k]*(n/val(j,k)-(i-1))%MOD;
dp[i][j][k]+=1ll*dp[i-1][j+1][k]*1ll*(n/val(j,k)-n/val(j+1,k))%MOD;
dp[i][j][k]%=MOD;
if (!k) dp[i][j][k]+=1ll*dp[i-1][j][k+1]*(n/val(j,k)-n/val(j,k+1))%MOD;
dp[i][j][k]%=MOD;
}
}
}
cout<<dp[n][0][0]<<endl;
return 0;
}
1107E Vasya and Binary String
link(*2400)
非常玄妙的 dp(
(说起来 “dp” 这种东西是不是不应该写成 (
看 dls 题解 吧(
感觉这种题就是出题人一拍脑子想出来一个绝妙的 dp 方法,然后用这个方法出了一个题
但是这种思路正常人根本想不到吧(
// 2020.12.26
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=105;
int n;
bool s[MAXN];
int a[MAXN];
int dp[MAXN][MAXN][MAXN];
signed main()
{
n=read();
for (int i=1;i<=n;i++)
s[i]=readch()=='1';
for (int i=1;i<=n;i++)
a[i]=read();
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j++)
for (int k=0;k+j<=n;k++)
dp[i][j][k]=-1e15;
for (int i=1;i<=n;i++)
for (int j=0;i+j<=n;j++){
dp[i][i][j]=a[j+1];
}
for (int len=2;len<=n;len++){
for (int i=1;i+len-1<=n;i++){
int j=i+len-1;
for (int k=0;k+j<=n;k++)
chmax(dp[i][j][k],dp[i][j-1][0]+a[k+1]);
for (int k=0;k+j<=n;k++){
for (int l=i;l<j;l++){
if (s[l]==s[j]) chmax(dp[i][j][k],dp[i][l][k+1]+dp[l+1][j-1][0]);
}
}
}
}
cout<<dp[1][n][0]<<endl;
return 0;
}