- 洛谷P4933大师(线性DP)
- 洛谷P5858Golden Sword(线性DP)
- 洛谷P1280尼克的任务(线性DP)
- USACO16OPEN 2048(区间DP)
- 洛谷P2585三色二叉树(树形DP)
- 洛谷P1441砝码称重(枚举，背包)
- 洛谷P1896互不侵犯(状压DP)
- codeforces1488E Palindromic Doubles(LIS+思维)
- codeforces1486D Max Median(二分+思维)
- codeforces1486E Paired Payment(多维最短路)
- codeforces1426F Number of Subsequences(计数DP)
洛谷P4933大师
题意：给一个n长度序列，第i个数为h[i]，求等差数列个数。（n<1e3,h[i]<2e4）
题解：由n和h[i]的范围可以知道，状态为dp[i][j],复杂度为n*max(h[j])，dp[i][j]代表以第i个数结尾j为公差的等差数列个数
枚举i，再枚举i的前一个，更新答案。
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
#define N 1005
#define Mod 998244353
#define maxh 20005
inline int read(){int x;scanf("%d",&x);return x;}
int h[N],dp[N][3*maxh];
void solve()
{
int n=read(),ans=0;
f(i,1,n) h[i]=read();
f(i,1,n) f(j,1,i-1)
{
dp[i][h[i]-h[j]+maxh]=(dp[i][h[i]-h[j]+maxh]+dp[j][h[i]-h[j]+maxh]+1)%Mod;
ans=(ans+dp[j][h[i]-h[j]+maxh]+1)%Mod;
}
ans=(ans+n)%Mod;
cout<<ans;
}
int main()
{
int T=1;
while(T--) solve();
return 0;
}
洛谷P5858Golden Sword
题意：给n个原料，每个都有一个权值a[i]（可能为负），依次放进锅里，锅的容量为w，在放进一个原料前，最多可以从锅里拿出s个，当一个原料放进锅里的时候，你会获得的 分数 =（放进当前原料锅中原料个数）*（当前原料的权值），求放n个原料后可以得到的最大权值，（n，w，s<5e5,a[i]<1e9）
题解：dp[i][j]代表放完i个原料且锅中现在有j个原料的最大分数，可以发现，dp[i][j]可以由dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1],...,dp[i-1][j+s-1]转移而来，因此维护这一段的最大值即可，单调队列维护即可。
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register ll i=a;i<=b;++i)
#define ll long long
#define N 5005
#define Mod 998244353
#define INF 999999999
#define maxh 20005
inline ll read(){ll x;scanf("%lld",&x);return x;}
ll a[N],dp[N][N];
void solve()
{
ll n=read(),w=read(),s=read();
f(i,1,n) a[i]=read();
dp[1][1]=a[1];
f(i,2,n)
{
deque<ll>dq;
if(i>w) dq.push_front(w);
for(int j=min(w,i);j>=1;--j)
{
if(j!=1)
{
while(dq.size()&&dp[i-1][dq.front()]<=dp[i-1][j-1]) dq.pop_front();
dq.push_front(j-1);
}
if(dq.back()>j-1+s) dq.pop_back();
dp[i][j]=dp[i-1][dq.back()]+a[i]*j;
}
}
ll ans=-INF;
f(i,1,min(w,i)) ans=max(ans,dp[n][i]);
cout<<ans<<endl;
}
int main()
{
ll T=1;
while(T--) solve();
return 0;
}
洛谷P1280尼克的任务
题意：有n单位的时间和m个任务，从第一个时间点开始，如果某个时间段没有执行任务，称为空暇时间，每个任务有个开始时间和结束时间，如果当前有x个任务开始前你没有执行任务，则必须选择一个，求怎么选择空暇时间最长。
题解：显然是线性DP，但是如果正向递推就会发现，特别的麻烦，于是采取倒推，设dp[i]代表从i开始到n的最长空暇时间，则从n到1递推，递推式为：
if(这个时间点没有任务开始) dp[i]=dp[i+1]+1;//
else
{
for(所有的任务) dp[i]=max(dp[i],dp[i+T]) //T为当前任务结束时间
}
AC代码
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define pb push_back
#define N 10005
inline int read(){int x;scanf("%d",&x);return x;}
int dp[N];
vector<int>pii[N];
int main()
{
int n=read(),m=read();
f(i,1,m)
{
int s=read(),t=read();
pii[s].pb(t);
}
for(int i=n;i>=1;--i)
{
if(pii[i].size()==0) dp[i]=dp[i+1]+1;
else
{
for(auto T:pii[i])
{
dp[i]=max(dp[i],dp[T+i]);
}
}
}
cout<<dp[1];
return 0;
}
另一种方法：DAG求最长路（略）
USACO16OPEN 2048
题意：n个数的序列，用来玩2048，相邻两个相等的数可合并成这个数+1，求最大能合并的数
题解：如果一段区间可以合并成一个数，那这个数显然是确定的，dp[i][j]代表[i,j]区间合并成的数，如果不能合并，dp[i][j]=0;
转移方程：
for(int k=L;k<R;++k)
if(dp[L][k]&&dp[k+1][R]&&dp[L][k]==dp[k+1][R]) dp[L][R]=dp[L][k]+1;
AC代码
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define pb push_back
#define N 256
inline int read(){int x;scanf("%d",&x);return x;}
int dp[N][N],num[N];
int main()
{
int n=read(),Max=0;
f(i,1,n) num[i]=read();
f(i,1,n) dp[i][i]=num[i],Max=max(Max,num[i]);
f(len,2,n) f(L,1,n)
{
int R=L+len-1;
if(R>n) break;
f(k,L,R-1) if(dp[L][k]&&dp[k+1][R]&&dp[L][k]==dp[k+1][R]) dp[L][R]=dp[L][k]+1;
Max=max(Max,dp[L][R]);
}
cout<<Max;
return 0;
}
洛谷P2585三色二叉树
题意：给一颗二叉树，涂上红绿蓝三种颜色，要求父子和兄弟不能同色，求涂完色，绿色最多和最少有几个。（(n<5*10^5)）
题解：先考虑最多的情况，定义dp[i][0/1]代表以i为根的子树最多涂几个绿色，则得到以下转移式：
(dp1_{s,0}=max(dp1_{ls,1}+dp1_{rs,0},dp1_{ls,0}+dp1_{rs,1}))
(dp1_{s,1}=dp1_{ls,0}+dp1_{rs,0}+1)
考虑最少，得到以下转移式
(dp2_{s,0}=min(dp2_{ls,1}+dp2_{rs,0},dp2_{ls,0}+dp2_{rs,1}))
(dp2_{s,1}=dp2_{ls,0}+dp2_{rs,0})
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 550010;
char t[N];
int f[N][2], g[N][2], size[N];
inline void dfs(int x)
{
f[x][0] = 0; f[x][1] = 1;
g[x][0] = 0; g[x][1] = 1;
size[x] = 0;
int to[3] = {0};
for (int i = 1; i <= t[x] - '0'; i++) {
int y = x + size[x] + 1;
to[i] = y;
dfs(y);
size[x] += size[y];
}
size[x] += 1;
if (t[x] == '0') return;
if (t[x] == '1') {
f[x][0] += max(f[to[1]][0], f[to[1]][1]);
f[x][1] += f[to[1]][0];
g[x][0] += min(g[to[1]][0], g[to[1]][1]);
g[x][1] += g[to[1]][0];
}
if (t[x] == '2') {
f[x][0] += max(f[to[1]][0] + f[to[2]][1], f[to[1]][1] + f[to[2]][0]);
f[x][1] += f[to[1]][0] + f[to[2]][0];
g[x][0] += min(g[to[1]][0] + g[to[2]][1], g[to[1]][1] + g[to[2]][0]);
g[x][1] += g[to[1]][0] + g[to[2]][0];
}
}
int main() {
cin >> t;
dfs(0);
cout << max(f[0][0], f[0][1]) << " " << min(g[0][0], g[0][1]) << endl;
return 0;
}
洛谷P1441砝码称重
题意：给(n)个砝码，选择(n-m)个，使得这(n-m)个砝码能组成的重量最多，输出最多组成几个重量((n<=20,m<=4,a_i<=100)).
题解：看数据范围像状压DP，实际上duck不必，枚举m个舍弃的砝码，每个枚举结果使用一次01背包记录，获得最大次数
枚举的复杂度：(C^{m}_{n})最多只有5000，每个结果dp，复杂度为(nsum a_i),最多为40000，总复杂度勉强能过。
#include <bits/stdc++.h>
using namespace std;
const int N = 550010;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
inline int read(){int x;scanf("%d",&x);return x;}
#define gc getchar()
#define pb push_back
#define Mod 80112002
int a[23],use[23],n,m,dp[2030],Ans;
void DP()
{
memset(dp,0,sizeof dp);
dp[0]=true;
int sum=0,res=0;
f(i,1,n)
{
if(use[i]) continue;
for(int j=sum;j>=0;--j) if(dp[j]&&!dp[j+a[i]]) res++,dp[j+a[i]]=true;
sum+=a[i];
}
if(res>Ans) Ans=res;
}
void dfs(int now,int pre)
{
if(now==m)
{
DP();
return ;
}
for(int i=pre+1;i<=n-m+now+1;++i)
{
use[i]=1;
dfs(now+1,i);
use[i]=0;
}
}
int main()
{
n=read(),m=read();
f(i,1,n) a[i]=read();
dfs(0,0);
cout<<Ans<<endl;
return 0;
}
洛谷P1896互不侵犯
题意：每一个n*n地图，要在上面摆放m个国王，要求每个国王所在的九宫格内（国王可以放在边界）不能有其他国王，求摆放方案数。((n<=9,m<=n*n))
题解：根据数据范围可以发现是状压DP，定义：dp[i][j][state]代表到第i行摆放j个国王最后一行状态为state的方案数，对于可行的状态state，再枚举上一行的state，如果上一行和这一行状态不冲突，就把这个状态累加到当前状态。
要素1：对于一行状态是否可行，只要判断有没有相邻的1，巧妙利用位运算
bool check1(ll x)//判断一个状态是否合法
{
if(x&(x>>1)) return false;
return true;
}
要素2：先把一行所有的可行状态存进vector数组，枚举时会省下很多时间
f(i,0,tot)
if(check1(i)) ok.pb(mp(i,bitcount(i)));//先把合法的状态保存起来，可以省下很多时间
要素3：判断两个状态是否可以相邻出现，巧妙利用位运算
bool check2(ll x,ll y)//判断两个状态能否相邻
{
if(x&y) return false;
if(x&(y<<1)) return false;
if(x&(y>>1)) return false;
return true;
}
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
inline ll read(){ll x;scanf("%lld",&x);return x;}
#define pb push_back
ll dp[10][100][550];
vector<pair<ll,ll> >ok;
#define mp make_pair
#define fi first
#define se second
ll bitcount(ll n)//返回一个状态1的个数
{
ll c =0 ;
for(c=0;n;++c) n&=(n-1);
return c ;
}
bool check1(ll x)//判断一个状态是否合法
{
if(x&(x>>1)) return false;
return true;
}
bool check2(ll x,ll y)//判断两个状态能否相邻
{
if(x&y) return false;
if(x&(y<<1)) return false;
if(x&(y>>1)) return false;
return true;
}
int main()
{
ll n=read(),m=read(),tot=(1<<n)-1,ans=0;
f(i,0,tot)
if(check1(i)) ok.pb(mp(i,bitcount(i)));//先把合法的状态保存起来，可以省下很多时间
dp[0][0][0]=1;//初始化很重要
f(i,1,n)
{
ll Max=min(((n+1)/2)*((i+1)/2),m);
f(j,0,Max)
{
if(!j){dp[i][0][0]=1;continue;}//特判j==0的情况
for(auto kp:ok)
{
if(kp.se>j) continue;
for(auto qp:ok)
{
if(!check2(kp.fi,qp.fi)) continue;
dp[i][j][kp.fi]+=dp[i-1][j-kp.se][qp.fi];
}
}
}
if(i==n) //到达最后一列，把答案加起来
{
for(auto kp:ok) ans+=dp[n][m][kp.fi];
}
}
cout<<ans<<endl;
return 0;
}
codeforces1488E Palindromic Doubles
题意：给一个n长度序列a，(1<=a_i<=n)，且每个数字最多出现两次，求最长回文子序列。
题解：先不考虑奇数长度的回文序列，偶数长度的回文序列由若干对相同的数字组成，我们拿出所有的存在两次的数字对，按照第一次出现的下标从小到大排序，再对第二次出现的下标求一次LIS，则偶数长度的最长回文子序列就是2*LIS。
现在考虑奇数长度，如果存在奇数长度的最长回文序列，则一定是最长的偶长回文序列长度+1，只要找出所有的最长偶长回文序列(也就是所有的LIS)，再找出满足条件的一条，满足LIS的起点和与之对应的第一次出现的下标不相邻，就是可以构成奇数长度最长回文序列的LIS。
怎么求出所有的LIS?
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
const int N = 255000;
inline int read(){int x;scanf("%d",&x);return x;}
struct NUM{
int x,y,id;
NUM()
{
x=y=0;
id=0;
}
void init()
{
x=y=0;
id=0;
}
void add(int a)
{
if(!x)
{
x=a;
return ;
}
if(!y)
{
y=a;
id=1;
return ;
}
}
}num[N];
int cmp(NUM a,NUM b)
{
return a.x>b.x;
}
int b[N],c[N],a[N],dp[N],cnt,ans,LIS[N],Max[N],vis[N];
void init(int n)
{
ans=cnt=0;
f(i,1,n)
{
vis[i]=0;
Max[i]=0;
LIS[i]=0;
dp[i]=0;
num[i].init();
}
}
void solve()
{
int n=read();
init(n);
f(i,1,n) num[read()].add(i);
sort(num+1,num+1+n,cmp);
f(i,1,n)
{
if(!num[i].id) continue;
b[++cnt]=num[i].y;
c[cnt]=num[i].x;
}
if(!cnt)
{
cout<<1<<endl;
return ;
}
for(int i=1;i<=cnt;++i)
{
if(b[i]>dp[ans]) dp[++ans]=b[i],LIS[i]=ans;
else
{
int x=upper_bound(dp+1,dp+1+ans,b[i])-dp;
dp[x]=b[i];
LIS[i]=x;
}
}
for(int i=cnt;i>=1;--i)
{
if(LIS[i]==ans)
{
Max[LIS[i]]=max(Max[LIS[i]],b[i]);
vis[i]=1;
continue;
}
if(b[i]<Max[LIS[i]+1])
{
Max[LIS[i]]=max(Max[LIS[i]],b[i]);
vis[i]=1;
}
}
for(int i=1;i<=cnt;++i)
{
if(LIS[i]==1&&vis[i]==1)
{
if(b[i]-c[i]>1)
{
cout<<2*ans+1<<endl;
return ;
}
}
}
cout<<2*ans<<endl;
}
int main()
{
int T=read();
while(T--) solve();
return 0;
}
codeforces1486D Max Median
题意：给一个n长度数组和一个k，求所有长度大于k的连续子序列中，最大的中位数是多少？
题解：首先二分答案，对每一个mid值判断是否可行，在一个大佬的博客里学到的技巧，对于每次二分后，将数组中大于等于mid的值变成1，其他的变成-1，这样当区间[L,R]的区间和大于等于1的时候，它的中位数就大于等于mid，这样就相当好做了。
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
const int N = 255000;
int n,k,a[N],b[N],Min[N];
inline int read(){int x;scanf("%d",&x);return x;}
bool check(int mid)
{
int sum=0,pre=0,mp=0;
f(i,1,n)
if(mid<=a[i]) b[i]=1;
else b[i]=-1;
f(i,1,k) sum+=b[i];
if(sum>=1) return true;
f(i,k+1,n)
{
sum+=b[i];
pre=pre+b[i-k];
mp=min(mp,pre);
if(sum-mp>=1) return true;
}
return false;
}
void solve()
{
n=read(),k=read();
f(i,1,n) a[i]=read();
int L=1,R=n;
while(L<R)
{
int mid=(L+R+1)>>1;
if(check(mid)) L=mid;
else R=mid-1;
}
printf("%d
",L);
}
int main()
{
int T=1;
while(T--) solve();
return 0;
}
codeforces1486E Paired Payment
题意：给一张n点m边无向图，每条边有权值w，移动时，一次只能连续走两条边，代价为((w1+w2)^2),求从1到各点的最短路，若走不到输出-1。
题解：显然普通的最短路算法无法解决这个问题，因为从一个点到另一个点的转移不仅要看上一条边的权值。还要看当前走的边是奇边还是偶边。
【多维最短路】：dis[i][j][0/1]代表当前到达i点，上一条边权值为j，且这条边是奇/偶边的最短路，这样这题就转化成以dis[i][j][k]为节点相互转移的最短路问题，用一次Dijkstra就可以了。
#include<vector>
#include<queue>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
inline ll read(){ll x;scanf("%lld",&x);return x;}
const int N = 100005;
vector<pair<ll,ll> >eg[N];
ll dis[N][55][2],n,m;
#define mp make_pair
#define pb push_back
const ll INF = 1e18;
ll ans[N];
struct Node{
ll len,last,odd,id;
Node(){}
Node(ll l1,ll l2,ll o,ll i)
{
len=l1;
last=l2;
odd=o;
id=i;
}
friend bool operator<(Node a,Node b)
{
return a.len>b.len;
}
};
void dij()
{
priority_queue<Node > qn;
f(i,1,n) f(j,1,50) f(k,0,1) dis[i][j][k]=INF;
dis[1][0][0]=0;
qn.push(Node(0,0,0,1));
while(qn.size())
{
ll len=qn.top().len,last=qn.top().last,odd=qn.top().odd,id=qn.top().id;
qn.pop();
if(len!=dis[id][last][odd]) continue;
for(auto pv:eg[id])
{
ll v=pv.first,w=pv.second;
if(odd)
{
if(dis[id][last][odd]+(last+w)*(last+w)<dis[v][w][0])
{
dis[v][w][0]=dis[id][last][odd]+(last+w)*(last+w);
qn.push(Node(dis[v][w][0],w,0,v));
}
}
else
{
if(dis[id][last][odd]<dis[v][w][odd^1])
{
dis[v][w][odd^1]=dis[id][last][odd];
qn.push(Node(dis[v][w][odd^1],w,1,v));
}
}
}
}
}
void solve()
{
n=read(),m=read();
f(i,1,m)
{
ll x=read(),y=read(),z=read();
eg[x].pb(mp(y,z));
eg[y].pb(mp(x,z));
}
dij();
f(i,2,n)
{
ans[i]=INF;
f(j,1,50) ans[i]=min(ans[i],dis[i][j][0]);
}
f(i,1,n) printf("%lld ",(ans[i]==INF)?(-1):ans[i]);
}
int main()
{
int T=1;
while(T--) solve();
return 0;
}
codeforces1426F Number of Subsequences
题意：给一串由'a','b','c','?'组成的字符串，k可以变成成'a','b','c'，若有k个'?'，则在所有的(2^k)个字符串中，"abc"子串的数量和。
题解：假设这道题没有'?',则可以这样做，另dp[i][0/1/2]分别代表到第i个字符，"a","ab","abc"子串的数量，则有下列递推式
if(str[i]=='a')
{
dp[i][0]=dp[i-1][0]+1;
dp[i][1]=dp[i-1][1];
dp[i][2]=dp[i-1][2];
}
else if(str[i]=='b')
{
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1]+dp[i-1][0];
dp[i][2]=dp[i-1][2];
}
else
{
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1];
dp[i][2]=dp[i-1][2]+dp[i-1][1];
}
现在有了'?'，必须增加一个状态，dp[i][0/1/2/3]分别代表到第i个字符，序列的数量，"a"的数量,"ab"的数量,"abc"的数量，则有
//(有滚动数组优化)
if(ch=='a') dp[1]=(dp[0]+dp[1])%Mod;
else if(ch=='b') dp[2]=(dp[2]+dp[1])%Mod;
else if(ch=='c') dp[3]=(dp[3]+dp[2])%Mod;
else
{
dp[3]=(3*dp[3]+dp[2])%Mod;
dp[2]=(3*dp[2]+dp[1])%Mod;
dp[1]=(3*dp[1]+dp[0])%Mod;
dp[0]=(3*dp[0])%Mod;
}
AC代码如下
#include<vector>
#include<queue>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
inline ll read(){ll x;scanf("%lld",&x);return x;}
const int N = 100005;
const ll Mod = 1e9+7;
ll dp[4];
string str;
void solve()
{
ll n=read();
cin>>str;
dp[0]=1ll;
f(i,1,n)
{
char ch=str[i-1];
if(ch=='a') dp[1]=(dp[0]+dp[1])%Mod;
else if(ch=='b') dp[2]=(dp[2]+dp[1])%Mod;
else if(ch=='c') dp[3]=(dp[3]+dp[2])%Mod;
else
{
dp[3]=(3*dp[3]+dp[2])%Mod;
dp[2]=(3*dp[2]+dp[1])%Mod;
dp[1]=(3*dp[1]+dp[0])%Mod;
dp[0]=(3*dp[0])%Mod;
}
}
cout<<dp[3];
}
int main()
{
int T=1;
while(T--) solve();
return 0;
}