《简单DP》
「JOISC 2020 Day4」治疗计划
分析
首先考虑问题的维度\([治疗状态],[时间],[花费]\)
治疗状态肯定无法省去
时间其实可以忽略，因为最终的答案的可行性与时间无关，但可能会加大转移的难度
事实上时间是可以不入状态的
考虑用01串表示治疗状态，但其实可以直接用前缀治疗状态
设\(dp[i]\)表示\([1,i]\)已治好的最小花费
\(111100111\),类似的情况，因为是连续的区间，所以不会出现》
转换一下，设\(dp[i]\)表示第\(i\)个计划实施后\([1,r_i]\)已被治疗
\(dp[i]=dp[j]+c[i],(r_j-l_i+1\geq|t_i-t_j|)\)
解释一下，首先对于\(i\)找到一个\(j\)使得\([1,r_i]\)被覆盖，要保证\([1,r_j]\)被感染到\(l_i\)之前被及时治疗
最初我觉得有可能有第三个计划将\(l_i-1\)及时覆盖使得dp的条件放宽
但事实上这种方案可以归纳到第三个计划的更新
这样做是\(O(n^2)\)的
考虑优化，每一\(dp_i\)是由当前满足条件最小\(dp_j\)更新
类似与\(dijkstra\),可以用当前最小更新，模型为无向图，没有顺序，因为尽管线性\(dp\)按\(r_i\)排序,但\(r_i\)大的一定不会更新小的
将上式绝对值裁开，可以得到两个不等式
\[r_j-t_j+1\geq l_i-t_i(t_i<t_j)
\\
r_j+t_j+1\geq l_i+t_i(t_i\geq t_j)
\]
\\
r_j+t_j+1\geq l_i+t_i(t_i\geq t_j)
\]
用线段树维护最小，以\(t_i\)排序建树，树上查找后设为无穷，复杂度均摊\(O(nlog_2(n))\)
启示
首先可以分析问题的维度,考虑状态,值与转移
对于庞大的状态,可以转化为前缀
#include<bits/stdc++.h>
#define int long long
#define INF 1e14
#define ls 2*p
#define rs 2*p+1
using namespace std;
const int MAXM=1e5+5;
int n,m;
struct Task{
int t,l,r,c;
bool operator<(const Task x)const{
return t<x.t;
}
}a[MAXM];
int dp[MAXM];
struct node{
int val,u;
bool operator<(const node x)const{
return val>x.val;
}
};
priority_queue<node>q;
struct Seg{
int l,r;
int date1;
int date2;
}Tree[MAXM*4];
void push_up(int p)
{
Tree[p].date1=min(Tree[ls].date1,Tree[rs].date1);
Tree[p].date2=min(Tree[ls].date2,Tree[rs].date2);
}
void Build(int p,int l,int r)
{
Tree[p].l=l;
Tree[p].r=r;
if(l==r)
{
Tree[p].date1=a[l].l+a[l].t;
Tree[p].date2=a[l].l-a[l].t;
return;
}
int mid=(l+r)>>1;
Build(ls,l,mid);
Build(rs,mid+1,r);
push_up(p);
}
void Update(int p,int k)
{
if(Tree[p].l==Tree[p].r)
{
Tree[p].date1=INF;
Tree[p].date2=INF;
return;
}
int mid=(Tree[p].l+Tree[p].r)>>1;
if(k<=mid)
{
Update(ls,k);
}
else
{
Update(rs,k);
}
push_up(p);
}
vector<int>avail;
void FindL(int p,int k1,int k2)
{
if(Tree[p].l==Tree[p].r)
{
// printf("%d %d&**\n",k2,Tree[p].date2);
if(Tree[p].date1<=k2)
{
avail.push_back(Tree[p].l);
}
return;
}
int mid=(Tree[p].l+Tree[p].r)>>1;
if(mid>=k1)
{
if(Tree[ls].date1<=k2)
{
FindL(ls,k1,k2);
}
if(Tree[rs].date1<=k2)
{
FindL(rs,k1,k2);
}
}
else
{
if(Tree[rs].date1<=k2)
{
FindL(rs,k1,k2);
}
}
}
void FindR(int p,int k1,int k2)
{
if(Tree[p].l==Tree[p].r)
{
//printf("%d %d&**\n",k2,Tree[p].date2);
if(Tree[p].date2<=k2)
{
avail.push_back(Tree[p].l);
}
return;
}
int mid=(Tree[p].l+Tree[p].r)>>1;
if(mid<k1)
{
if(Tree[ls].date2<=k2)
{
FindR(ls,k1,k2);
}
if(Tree[rs].date2<=k2)
{
FindR(rs,k1,k2);
}
}
else
{
if(Tree[ls].date2<=k2)
{
FindR(ls,k1,k2);
}
}
}
signed main()
{
// freopen("01-01.in","r",stdin);
memset(dp,0x3f,sizeof(dp));
scanf("%lld %lld",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%lld %lld %lld %lld",&a[i].t,&a[i].l,&a[i].r,&a[i].c);
}
sort(a+1,a+1+m);
Build(1,1,m);
for(int i=1;i<=m;i++)
{
if(a[i].l==1)
{
// printf("%d %d-\n",i,a[i].c);
node sf;
sf.u=i;
sf.val=a[i].c;
dp[i]=a[i].c;
q.push(sf);
Update(1,i);
}
}
int tot=0;
while(q.size())
{
node temp=q.top();
// printf("%lld %lld--\n",temp.u,temp.val);
q.pop();
if(a[temp.u].r==n)
{
printf("%lld",temp.val);
return 0;
}
avail.clear();
FindL(1,temp.u,a[temp.u].r+a[temp.u].t+1);
for(int i=0;i<avail.size();i++)
{
int vv=avail[i];
dp[vv]=dp[temp.u]+a[vv].c;
Update(1,vv);
node fgf;
fgf.u=vv;
fgf.val=dp[vv];
q.push(fgf);
// printf("%d %d\n",vv,dp[vv]);
}
// printf("\n");
avail.clear();
FindR(1,temp.u,a[temp.u].r-a[temp.u].t+1);
for(int i=0;i<avail.size();i++)
{
int vv=avail[i];
dp[vv]=dp[temp.u]+a[vv].c;
Update(1,vv);
node fgf;
fgf.u=vv;
fgf.val=dp[vv];
q.push(fgf);
// printf("%d %d\n",vv,dp[vv]);
}
// ++tot;
// printf("%d\n",tot);
}
printf("-1");
}
CF1523F Favorite Game
分析
考虑数据范围\(n\leq14\),状压
维度为\([已达传送门][时间][当前任务][已完任务]\)
已达传送门可以放心放入状态,时间范围有点大，可以作为值
设\(dp[S][i][j]\)为当前所达传送门的01串为\(S\),当前完成到了\(i\)个任务,位置为\(j\)的最小时间
时间复杂度为\(O(2^{14}\times100^3)\)好像过不了
设\(wt[S][i]\)表示当前\(S\)状态，从传送门走到任务\(i\)的最小时间
设\(wp[S][i]\)表示当前\(S\)状态，从传送门走到传送门\(i\)的最小时间
考虑研究每一维度的性质
对于传送门，不用关心位置
对于任务，不用关心时间
设\(f[S][i]\)为在传送门完成\(i\)个任务的最小时间，\(g[S][i]\)为前\(i\)个任务在完成\(i\)的情况下可以完成的最大任务数
这里的\(f\)不关心位置，因为可以瞬移至任何一个已经激活的传送门，\(g\)不关心时间，因为完成\(i\)一定要等到\(t_i\)
考虑转移
有四种情况
\[Case1:传\rightarrow 传
\\
f(S,i)=min(f(S,i),f(S-(1<<j),i)+wp(S-(1<<j),i))
\]
\\
f(S,i)=min(f(S,i),f(S-(1<<j),i)+wp(S-(1<<j),i))
\]
很显然，不用解释
\[Case2:传\rightarrow 任
\\
g(S,j)=max(g(S,j),i+1)，当(f(S,i)+wt(S,j)\leq t_j)时
\]
\\
g(S,j)=max(g(S,j),i+1)，当(f(S,i)+wt(S,j)\leq t_j)时
\]
解释一下为什么不更新\(f\)
\(f\)会在下面更新
\[Case3:任\rightarrow 传
\\
f(S,g(S-(1<<j),i))=min(f(S,g(S-(1<<j),i)),min(dist(task_i,Port_j),wp(S,j))+t_i)
\]
\\
f(S,g(S-(1<<j),i))=min(f(S,g(S-(1<<j),i)),min(dist(task_i,Port_j),wp(S,j))+t_i)
\]
解释一下为什么没有
\(f(S,g(S,i))=min(f(S,g(S,i)),t_i)\)
这个相当于从已有任务把收益带回传送门，但在后续更新中g的收益会被统计，所以不用多一个方程
当然，多了会有后效性
\[Case4:任\rightarrow 任
\\
g(S,i)=max(g(S,i),g(S,j)+1),当j\leq i，min(wt(S,i),dist(Task_i,Task_j))+t_j\leq t_i
\]
\\
g(S,i)=max(g(S,i),g(S,j)+1),当j\leq i，min(wt(S,i),dist(Task_i,Task_j))+t_j\leq t_i
\]
这个不用解释
最后如果把\(S\)放在最外面，观察方程式，\(g(S)\)依赖\(f(S)\),而\(f(S)\)不用，所以\(Case3\)不能加那个方程
先更新\(f\),再更新\(g\)
启示
分析状态的性质压缩
值与状态的互相转化
#include<bits/stdc++.h>
using namespace std;
int Abs(int x)
{
return x>0?x:-x;
}
const int MAXN=105;
const int MAXS=14;
struct node{
int x,y;
int t;
bool operator<(const node SS)const{
return t<SS.t;
}
}Port[MAXS+5],Task[MAXN];
int f[(1<<MAXS)+5][MAXN];
int g[(1<<MAXS)+5][MAXN];
int wp[(1<<MAXS)+5][MAXN];
int wt[(1<<MAXS)+5][MAXN];
int n,m;
int dist(node x,node y)
{
return Abs(x.x-y.x)+Abs(x.y-y.y);
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&Port[i].x,&Port[i].y);
}
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&Task[i].x,&Task[i].y,&Task[i].t);
}
Task[0].t=0;
sort(Task+1,Task+1+m);
for(int i=0;i<(1<<n);i++)
{
for(int j=1;j<=n;j++){
if((1<<(j-1))&i)
{
wp[i][j]=0;
}
else
{
wp[i][j]=0x3f3f3f3f;
for(int k=1;k<=n;k++)
{
if((1<<(k-1))&i)
{
wp[i][j]=min(wp[i][j],dist(Port[j],Port[k]));
}
}
}
}
}
for(int i=0;i<(1<<n);i++)
{
for(int j=1;j<=m;j++)
{
wt[i][j]=0x3f3f3f3f;
for(int k=1;k<=n;k++)
{
if((1<<(k-1))&i)
{
wt[i][j]=min(wt[i][j],dist(Task[j],Port[k]));
}
}
}
}
int Res=1;
memset(f,0x3f,sizeof(f));
memset(g,0xcf,sizeof(g));
for(int i=0;i<n;i++)
{
f[(1<<(i))][0]=0;
}
for(int i=1;i<=m;i++)
{
g[0][i]=1;
}
for(int i=0;i<(1<<n);i++)
{
for(int k=1;k<=n;k++)
{
if((1<<(k-1))&i)
{
for(int j=0;j<=m;j++)
{
f[i][j]=min(f[i][j],f[i-(1<<(k-1))][j]+wp[i-(1<<(k-1))][k]);
//printf("%d-\n",g[i-(1<<(k-1))][j]);
}
for(int j=1;j<=m;j++)
{
if(g[i-(1<<(k-1))][j]>=0)
{
f[i][g[i-(1<<(k-1))][j]]=min(f[i][g[i-(1<<(k-1))][j]],(min(dist(Task[j],Port[k]),wp[i-(1<<(k-1))][k])+Task[j].t));
}
}
}
}
for(int j=0;j<=m;j++)
{
for(int k=1;k<=m;k++)
{
if(f[i][j]+wt[i][k]<=Task[k].t)
{
g[i][k]=max(g[i][k],j+1);
}
if(k>j&&j)
{
if(min(wt[i][k],dist(Task[j],Task[k]))+Task[j].t<=Task[k].t)
{
g[i][k]=max(g[i][k],g[i][j]+1);
}
Res=max(Res,g[i][k]);
}
}
}
}
printf("%d",Res);
}
CF1476F Lanterns
分析
最开始觉得可以贪心，但很明显是错的
很难想到\(dp\),就算想到的也会因后效性劝退
我们考虑将前缀表示被照亮状态
设\(dp_i\)表示点亮前\(i\)个灯笼能照亮\((1,p)\)最大的\(p\)(其实是两个前缀)
如果\(i\)向右没问题
\[dp_i=i+p_i(dp_{i-1}\geq i)
\\
dp_i=dp_{i-1}(dp_{i-1}<i)
\]
\\
dp_i=dp_{i-1}(dp_{i-1}<i)
\]
如果\(i\)向左，被照的灯可以全部向右照，这样不就有后效性吗》
其实根据\(dp_i\)的定义，中间的灯的\(dp\)是不能更新的
我们想要照到右边的最多，也就是要中间被\(i\)照的灯多
由于\(dp\)单调递增，所以可以二分能接上的\(j\)最远的位置
设\(k\)为满足\(i-p_i-1\leq dp_k\)最小的\(k\)
\[dp_i=max(i-1,Max_{j=k+1}^{j-1}(j+p_j))
\]
\]
用\(ST\)表优化一下即可
启示
巧设状态消后效性
前缀表状态
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
int t;
int n;
int p[MAXN];
int dp[MAXN];
int dp_max[MAXN][25];
int Log2[MAXN];
int Query_max(int x,int y)
{
if(x>y)
{
return -0x3f3f3f3f;
}
int k = Log2[y-x+1];
return max(dp_max[x][k], dp_max[y - (1 << k) + 1][k]);
}
int Pre[MAXN];
char P[MAXN];
void Print(int x)
{
// printf("%d\n",x);
if(x==0)
{
return;
}
if(Pre[x]==-1)
{
P[x]='R';
Print(x-1);
}
else
{
int FG=Pre[x];
for(int i=FG+1;i<x;i++)
{
P[i]='R';
}
P[x]='L';
Print(FG);
}
}
int main()
{
for(int i=1;i<=MAXN-5;i++)
{
Log2[i]=log2(i);
}
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
}
for (int i = 1; i <= n; i++) {
dp_max[i][0] =i+p[i];
dp[i]=0;
}
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
dp_max[i][j] = max(dp_max[i][j - 1], dp_max[i + (1 << j - 1)][j - 1]);
}
}
for(int i=1;i<=n;i++)
{
int Op=0;
if(dp[i-1]>=i)
{
if(dp[i-1]>dp[i])
{
Op=-1;
dp[i]=dp[i-1];
}
if(i+p[i]>dp[i])
{
Op=-1;
dp[i]=i+p[i];
}
}
else
{
if(dp[i-1]>dp[i])
{
Op=-1;
dp[i]=dp[i-1];
}
}
int r=i-1;
int l=0;
int key=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(dp[mid]>=i-p[i]-1)
{
key=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
if(key!=-1)
{
int L=key+1;
int R=i-1;
int FU=Query_max(L,R);
FU=max(FU,i-1);
if(FU>dp[i])
{
Op=key;
dp[i]=FU;
}
}
Pre[i]=Op;
}
if(dp[n]>=n)
{
printf("YES\n");
Print(n);
for(int i=1;i<=n;i++)
{
printf("%c",P[i]);
}
printf("\n");
}
else
{
printf("NO\n");
}
}
}
CF1174E Ehab and the Expected GCD Problem
首先要分析怎样才能得到最大权值
设\(x=\prod\limits_{i=1}^mp_i^{q_i}\)
倘若权值最大，每一次\(\gcd\)的变换一定会使\(q_i\)至少减\(1\)
当\(x\)放在最前面，则权值为\((\sum\limits_{i=1}^{m}q_i)+1\)
因为为了保证质因数最多,考虑\(2,3,5......\)
因为\(5>2*2\),所以\(5\)后面的都没有用
因此权值为\(log_2(n)\)
但3有点难处理，因为毕竟3也可以加进去
同时序列中间的可以保持原有\(\gcd\)
设\(dp_{i,j,k}\)表示前\(i\)位当前\(\gcd2\)的指数为\(j\),\(3\)的指数为\(k\),\(j\leq log_2(n),k=0/1\)
\[dp[i][j][k]=dp[i][j][k]+dp[i-1][j][k]*(n/Re[j][k]-(i-1))
\\
dp[i][j][k]=dp[i][j][k]+dp[i-1][j+1][k]*(n/Re[j][k]-n/Re[j+1][k]))
\\
dp[i][j][k]=dp[i][j][k]+dp[i-1][j][k+1]*(n/Re[j][k]-n/Re[j][k+1]))
\]
\\
dp[i][j][k]=dp[i][j][k]+dp[i-1][j+1][k]*(n/Re[j][k]-n/Re[j+1][k]))
\\
dp[i][j][k]=dp[i][j][k]+dp[i-1][j][k+1]*(n/Re[j][k]-n/Re[j][k+1]))
\]
不用解释把。。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
const int MOD=1e9+7;
int n;
int dp[MAXN][23][2];
int Re[35][6];
signed main()
{
scanf("%d",&n);
int Maxs=0;
int Now=1;
while(1)
{
if(Now>n)
{
Maxs--;
Now/=2;
break;
}
Now*=2;
Maxs++;
}
dp[1][Maxs][0]=1;
if(Now/2*3<=n)
{
dp[1][Maxs-1][1]=1;
}
for(int i=0;i<=Maxs;i++)
{
for(int j=0;j<=1;j++)
{
Re[i][j]=(1<<i);
if(j)
{
Re[i][j]=(Re[i][j]*3);
}
}
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<=Maxs;j++)
{
for(int k=0;k<=1;k++)
{
dp[i][j][k]=((long long)dp[i][j][k]+((long long)dp[i-1][j][k]*((long long)(n/Re[j][k])%MOD-(i-1)+MOD)%MOD)%MOD)%MOD;
if(j+1<=Maxs)
{
dp[i][j][k]=((long long)dp[i][j][k]+((long long)dp[i-1][j+1][k]*((long long)(n/Re[j][k])%MOD-((long long)n/Re[j+1][k])%MOD+MOD)%MOD)%MOD)%MOD;
}
if(k+1<=1)
{
dp[i][j][k]=((long long)dp[i][j][k]+((long long)dp[i-1][j][k+1]*((long long)(n/Re[j][k])%MOD-((long long)n/Re[j][k+1])%MOD+MOD)%MOD)%MOD)%MOD;
}
}
}
}
printf("%d",dp[n][0][0]);
}
「Gym - 100886A」Three Servers
首先考虑比较大背包\(dp\)
设\(dp_{i,j,k}\)表示前\(i\)个任务第一个和为\(j\),另一个为\(k\),是否存在
转移显然
\[dp_{i,j,k}|=dp_{i-1,j-a[i],k}
\\
dp_{i,j,k}|=dp_{i-1,j,k-a[i]}
\]
\\
dp_{i,j,k}|=dp_{i-1,j,k-a[i]}
\]
显然会超
滚动一下,设\(dp_{i,j}\),\(i,j\)的数据范围为\(12000\)
考虑极差，为了平均，显然大于\(4030\)的可以匀到其他地方
这样数据范围压缩到\(4030\)
时间复杂度为\(O(4030^2\times400)\)
考虑\(t_i\)相同的一起更新
然后设\(g_{i,j}\)为达到\((i,j)\)当前最大能余下的物品
显然\(g,f\)可以只转移\(30\)次(感觉就是将同种物品量化)
这样就可以\(O(4030^2\times30)\)(有点卡)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=405;
const int MAXK=4030;
int n;
int t[MAXN];
vector<int>R[35];
short g[MAXN*10][MAXN*10];
bool f[MAXN*10][MAXN*10];
pair<short,short>Rec[MAXN*10][MAXN*10];
short RRR[MAXN*10][MAXN*10];
int sum=0;
pair<short,short> T[MAXN*10][MAXN*10];
int vis[MAXN];
void print(int x,int y)
{
if((!x)&&(!y))
{
return;
}
int dgd=RRR[x][y];
pair<int,int>dzd=Rec[x][y];
// printf("%d %d %d %d %d\n",x,y,dgd,dzd.first,dzd.second);
int Nowsd=dzd.first;
while(Nowsd--){
int fg=R[dgd].back();
vis[fg]=1;
R[dgd].pop_back();
//Nowsd--;
// printf("%d-\n",fg);
}
Nowsd=dzd.second;
while(Nowsd--){
int fg=R[dgd].back();
vis[fg]=2;
R[dgd].pop_back();
}
print(x-dgd*dzd.first,y-dgd*dzd.second);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);
R[t[i]].push_back(i);
sum+=t[i];
}
f[0][0]=1;
for(int id=0;id<=30;id++)
{
if(!R[id].size())
{
continue;
}
// printf("-");
for(int i=0;i<=MAXK;i++)
{
for(int j=0;j<=MAXK;j++)
{
g[i][j]=-1;
if(f[i][j])
{
g[i][j]=R[id].size();
T[i][j].first=0;
T[i][j].second=0;
}
}
}
for(int i=0;i<=MAXK;i++)
{
for(int j=0;j<=MAXK;j++)
{
if(i>=id)
{
// g[i][j]=max(g[i][j],);
if(g[i-id][j]-1>g[i][j])
{
g[i][j]=g[i-id][j]-1;
T[i][j]=T[i-id][j];
T[i][j].first++;
}
}
if(j>=id)
{
// g[i][j]=max(g[i][j],g[i][j-id]-1);
if(g[i][j-id]-1>g[i][j])
{
g[i][j]=g[i][j-id]-1;
T[i][j]=T[i][j-id];
T[i][j].second++;
}
}
}
}
for(int i=0;i<=MAXK;i++)
{
for(int j=0;j<=MAXK;j++)
{
if(g[i][j]>=0&&(!f[i][j]))
{
f[i][j]=1;
Rec[i][j]=T[i][j];
RRR[i][j]=id;
// T[i][j].first*=id;
// T[i][j].second*=id;
}
}
}
}
int Minan=0x3f3f3f3f;
int Recx=0,Recy=0;
for(int i=0;i<=MAXK;i++)
{
for(int j=0;j<=MAXK;j++)
{
// printf("?");
if(f[i][j])
{
int sfg=max(i,max(j,sum-i-j))-min(i,min(j,sum-i-j));
if(sfg<Minan)
{
Minan=sfg;
Recx=i;
Recy=j;
}
}
}
}
printf("%d\n",Minan);
print(Recx,Recy);
vector<int>wgyIloveyou;
for(int i=1;i<=n;i++)
{
if(vis[i]==1)
{
wgyIloveyou.push_back(i);
}
}
printf("%d",wgyIloveyou.size());
for(int i=0;i<wgyIloveyou.size();i++)
{
printf(" %d",wgyIloveyou[i]);
}
printf("\n");
wgyIloveyou.clear();
for(int i=1;i<=n;i++)
{
if(vis[i]==2)
{
wgyIloveyou.push_back(i);
}
}
printf("%d",wgyIloveyou.size());
for(int i=0;i<wgyIloveyou.size();i++)
{
printf(" %d",wgyIloveyou[i]);
}
printf("\n");
wgyIloveyou.clear();
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
wgyIloveyou.push_back(i);
}
}
printf("%d",wgyIloveyou.size());
for(int i=0;i<wgyIloveyou.size();i++)
{
printf(" %d",wgyIloveyou[i]);
}
printf("\n");
}
HDU - 4899 Hero meet devil
首先考虑\(LCS\)的求法
\[f_{i,j}=f_{i-1,j-1}+1(s_i=t_j)
\\
f_{i,j}=max(f_{i-1,j},f_{i,j-1})(s_i\neq t_j)
\]
\\
f_{i,j}=max(f_{i-1,j},f_{i,j-1})(s_i\neq t_j)
\]
事实上，\(f\)是支持\(t\)的动态插入的，也就是说，如果固定\(s\),\(t\)只需关注最后的字符
这就很像\(dp\)的定义
而\(|S|\leq15\)看着很状压，而怎么压都不好转移
于是将\(f\)状压进\(dp\)
而\(f\)的值不好压，考虑差分
显然\(f_{i,j-1}\leq f_{i,j}\leq f_{i,j-1}+1\)
于是可以将\(f\)压成01串
设\(dp[S][i]\)表示当前\(S\)下\(T\)匹配了\(i\)位的方案数(\(S\)为\(f\)的差分)
预处理\(Nex[S][i]\)为当前\(S\)时放\(i\)可达状态
转移不难
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
const int MOD=1e9+7;
const int MAXS=15;
int t;
string s;
int m;
int Nex[(1<<MAXS)+5][5];
int f[MAXS+55];
int g[MAXS+55];
char SA[15]={'A','C','G','T'};
int dp[(1<<MAXS)+5][MAXN];
int main()
{
scanf("%d",&t);
while(t--)
{
cin>>s;
int n=s.size();
scanf("%d",&m);
for(int i=0;i<(1<<n);i++)
{
for(int j=1;j<=m;j++)
{
dp[i][j]=0;
}
for(int ch=0;ch<4;ch++)
{
for(int j=0;j<n;j++)
{
if(i&(1<<j))
{
f[j+1]=1;
}
else
{
f[j+1]=0;
}
}
for(int j=1;j<=n;j++)
{
f[j]=f[j-1]+f[j];
// printf("%d ",f[j]);
}
// printf("\n");
// printf("%c\n",SA[ch]);
for(int j=1;j<=n;j++)
{
if(s[j-1]==SA[ch])
{
g[j]=f[j-1]+1;
}
else
{
g[j]=max(g[j-1],f[j]);
}
}
for(int j=1;j<=n;j++)
{
// printf("%d ",g[j]);
f[j]=g[j]-g[j-1];
}
// printf("\n\n");
int DT=0;
for(int j=0;j<n;j++)
{
if(f[j+1])
{
DT=(DT+(1<<j));
}
}
Nex[i][ch]=DT;
}
}
dp[0][0]=1;
for(int i=0;i<m;i++)
{
for(int j=0;j<(1<<n);j++)
{
for(int cc=0;cc<4;cc++)
{
dp[Nex[j][cc]][i+1]=(dp[Nex[j][cc]][i+1]+dp[j][i])%MOD;
}
}
}
for(int i=1;i<=n;i++)
{
g[i]=0;
}
for(int i=0;i<(1<<n);i++)
{
for(int j=0;j<n;j++)
{
if(i&(1<<j))
{
f[j+1]=1;
}
else
{
f[j+1]=0;
}
}
for(int j=1;j<=n;j++)
{
f[j]=f[j-1]+f[j];
// printf("%d ",f[j]);
}
// printf("\n");
g[f[n]]=(g[f[n]]+dp[i][m])%MOD;
}
for(int i=0;i<=n;i++)
{
printf("%d\n",g[i]);
}
}
}
CF626F Group Projects
考虑\(dp\)的维度\([极差之和][组数]\)
如果单纯以这俩个作为状态，好像不好转移，因为不知道当前匹配组的状态
这提示我们要记录最大值
如果将\(a\)排序，同时记录当前还未完成匹配的组数，好像就好做了
设\(dp_{i,j,k}\)为前\(i\)个数还有\(j\)个数未匹配当前匹配极差和减去未匹配的左端点的和为\(k\)
因为排了序，所以转移比较方便
\[dp(i,j,k)+=dp(i-1,j,k)(独立为组)
\\
dp(i,j,k)+=dp(i-1,j,k)*j(加入组且不为最大最小)
\\
dp(i,j,k)+=dp(i-1,j+1,k-a_i)(变成一个组的最大)
\\
dp(i,j,k)+=dp(i-1,j-1,k+a_i)(作为组的开头)
\]
\\
dp(i,j,k)+=dp(i-1,j,k)*j(加入组且不为最大最小)
\\
dp(i,j,k)+=dp(i-1,j+1,k-a_i)(变成一个组的最大)
\\
dp(i,j,k)+=dp(i-1,j-1,k+a_i)(作为组的开头)
\]
但\(k\)的取值可能为负，甚至到\(-10000\)
原因是只有走到组的末尾才能回收负值,倒着来也会使\(k\)过大
如果设\(a_r=a_{max},a_l=a_{min}\)
\(a_r-a_l=\sum\limits_{i=l+1}^r(a_i-a_{i-1})\)
因为\(a\)排了序，所以\((a_i-a_{i-1})\)一定大于\(0\),所以每次操作不会使值变小，所以超过\(K\)就可以不用算了
#include<bits/stdc++.h>
const int MOD=1e9+7;
using namespace std;
const int MAXN=205;
const int MAXK=1005;
int n,K;
int a[MAXN];
int dp[MAXN][MAXN][MAXK];
int d[MAXN];
signed main()
{
scanf("%d %d",&n,&K);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
d[i]=a[i]-a[i-1];
}
dp[0][0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
for(int k=0;k<=K;k++)
{
if(j&&k>=(j-1)*(d[i]))
{
dp[i][j][k]=((long long)dp[i][j][k]+dp[i-1][j-1][k-((j-1)*(d[i]))])%MOD;
}
if(k>=(j*d[i]))
{
dp[i][j][k]=((long long)dp[i][j][k]+((long long)dp[i-1][j][k-(j*d[i])]*j)%MOD)%MOD;
dp[i][j][k]=((long long)dp[i][j][k]+dp[i-1][j][k-(j*d[i])])%MOD;
}
if(k>=((j+1)*d[i]))
{
dp[i][j][k]=((long long)dp[i][j][k]+((long long)dp[i-1][j+1][k-((j+1)*d[i])]*(j+1))%MOD)%MOD;
}
}
}
}
int Res=0;
for(int i=0;i<=K;i++)
{
Res=((long long)Res+dp[n][0][i])%MOD;
}
printf("%d",Res);
}
