9.14 DP合集水表
关键子工程
在大型工程的施工前，我们把整个工程划分为若干个子工程，并把这些子工程编号为 1、
2、 ……、 N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些
子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此有两个任务需要我们去完
成：首先，我们需要计算整个工程最少的完成时间；同时，由于一些不可预测的客观因素会
使某些子工程延期，因此我们必须知道哪些子工程的延期会影响整个工程的延期，我们把有
这种特征的子工程称为关键子工程，因此第二个任务就是找出所有的关键子工程，以便集中
精力管理好这些子工程，尽量避免这些子工程延期，达到用最快的速度完成整个工程。为了
便于编程，现在我们假设：
（ 1）根据预算，每一个子工程都有一个完成时间。
（ 2）子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。
（ 3）只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，
也既同时施工的子工程个数不受限制。
（ 4）整个工程的完成是指：所有子工程的完成。
例如，有五个子工程的工程规划表：
序号 完成时间 子工程 1 子工程 2 子工程 3 子工程 4 子工程 5
子工程 1 5 0 0 0 0
子工程 2 4 0 0 0 0
子工程 3 12 0 0 0 0
子工程 4 7 1 1 0 0
子工程 5 2 1 1 1 1
其中，表格中第 I+1 行 J+2 列的值如为 0 表示“子工程 I”可以在“子工程 J”没完成
前施工，为 1 表示“子工程 I”必须在“子工程 J”完成后才能施工。上述工程最快完成时
间为 14 天，其中子工程 1、 3、 4、 5 为关键子工程。
又例如，有五个子工程的工程规划表：
序号 完成时间 子工程 1 子工程 2 子工程 3 子工程 4 子工程 5
子工程 1 5 0 1 0 0
子工程 2 4 0 0 0 0
子工程 3 12 0 0 1 0
子工程 4 7 1 1 0 0
子工程 5 2 1 1 1 1
上述的子工程划分不合理，因为无法安排子工程 1， 3， 4 的施工。
。。。拓扑排序SBT
新建一个0号点，所有工程搞完它才能搞，且时间为0
可以看做0号工程结束所有都结束了
- 乱搞出每个点搞完的时间，顺便判无解
- 从0号点开始搜，每次搜入边中完成时间最长的几个，搜到的都是答案（去掉0）
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<queue>
#define Fname "project"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=0;rg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
const int maxn=203,maxm=maxn*maxn<<1;
int s[maxn],t[maxn];
int fir[maxn],nxt[maxm],dis[maxm],id=0,in[maxn];
bool vis[maxn],yes[maxn];
il vd add(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}
queue<int>que;
il vd dfs(int now){
if(vis[now])return;
vis[now]=yes[now]=1;
int Max=0;
erep(i,now)if((i&1)==0)Max=max(Max,t[dis[i]]);
erep(i,now)if((i&1)==0)if(t[dis[i]]==Max)dfs(dis[i]);
}
bool f[maxn][maxn];
int main(){
#ifdef xzz
freopen(Fname".in","r",stdin);
freopen(Fname".out","w",stdout);
#endif
int n=gi();
rep(i,1,n)s[i]=gi();
rep(i,1,n){
rep(j,1,i-1)if(gi())add(j,i),add(i,j),f[j][i]=1,++in[i];
rep(j,i+1,n)if(gi())add(j,i),add(i,j),f[j][i]=1,++in[i];
if(!in[i])que.push(i),t[i]=s[i];
}
rep(k,1,n)rep(i,1,n)rep(j,1,n)f[i][j]|=f[i][k]&f[k][j];
rep(i,1,n)if(f[i][i]){puts("-1");return 0;}
rep(i,1,n)rep(j,1,n)if(f[i][j]&f[j][i]){puts("-1");return 0;}
rep(i,1,n)add(i,0),add(0,i);
in[0]=n;
while(!que.empty()){
int now=que.front();
erep(i,now)if(i&1){
--in[dis[i]],t[dis[i]]=max(t[dis[i]],t[now]+s[dis[i]]);
if(in[dis[i]]==0)que.push(dis[i]);
}que.pop();
}
printf("%d\n",t[0]);
dfs(0);
rep(i,1,n)if(yes[i])printf("%d ",i);puts("");
return 0;
}机器分配
某总公司拥有高效生产设备 M 台，准备分给下属的 N 个分公司。各分公司若获得这些设备，可以为总公司提供一定的盈利。问：如何分配这 M 台设备才能使国家得到的盈利最大？求出最大盈利值。
分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数 M。其中M<=100， N<=100。
。。。SBT，f[i][j]表示前i各公司分j个设备的最大盈利，暴力转移
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define Fname "machine"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=0;rg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int a[101][101],f[101][101];
int main(){
int m=gi(),n=gi();
rep(i,1,n)rep(j,1,m)a[i][j]=gi();
rep(i,1,m)f[1][i]=a[1][i];
rep(i,1,n)rep(j,1,m)rep(k,0,j)
f[i][j]=max(f[i][j],f[i-1][j-k]+a[i][k]);
printf("%d\n",f[n][m]);
return 0;
}编辑距离
SBT，跳过。。。
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=0;rg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
char a[2011],b[2011];
int lena,lenb;
int f[2011][2011];
int main(){
scanf("%s%s",a+1,b+1);
lena=strlen(a+1),lenb=strlen(b+1);
rep(i,1,lena)f[i][0]=i;
rep(i,1,lenb)f[0][i]=i;
rep(i,1,lena)rep(j,1,lenb)
if(a[i]==b[j])f[i][j]=f[i-1][j-1];
else f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;
printf("%d\n",f[lena][lenb]);
return 0;
}硬币找零
在现实生活中，我们经常遇到硬币找零的问题，例如，在发工资时，财务人员就需要计算最少的找零硬币数，以便他们能从银行拿回最少的硬币数，并保证能用这些硬币发工资。 我们应该注意到，人民币的硬币系统是 100，50，20，10，5，2，1，0.5，0.2，0.1，0.05， 0.02，0.01 元，采用这些硬币我们可以对任何一个工资数用贪心算法求出其最少硬币数。 但不幸的是： 我们可能没有这样一种好的硬币系统， 因此用贪心算法不能求出最少的硬币数，甚至有些金钱总数还不能用这些硬币找零。例如，如果硬币系统是 40，30，25 元，那么 37元就不能用这些硬币找零；95 元的最少找零硬币数是 3。又如，硬币系统是 10，7，5，1元，那么 12 元用贪心法得到的硬币数为 3，而最少硬币数是 2。 你的任务就是：对于任意的硬币系统和一个金钱数，请你编程求出最少的找零硬币数； 如果不能用这些硬币找零，请给出一种找零方法，使剩下的钱最少。
。。。SBT，f[i]表示凑出i的最少硬币数，凑不出为inf，求出后t不断--到f[t]不为inf为止输出
// It is made by XZZ
#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=0;rg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int s[52];
int f[100010];
int main(){
int n=gi(),t=gi();
rep(i,1,n)s[i]=gi();
rep(i,1,t){
f[i]=233;
rep(j,1,n)if(i>=s[j])f[i]=min(f[i],f[i-s[j]]+1);
}
while(f[t]==233)--t;
printf("%d\n",f[t]);
return 0;
}拦截导弹
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
第一行，输出计算这套系统最多能拦截多少导弹
第二行，输出要拦截所有导弹最少要配备多少套这种导弹拦截系统。
。。。因为N<=10^5所以没那么sb了，但还是sbt
第一部分同最长上升子序列
第二部分贪心+stl。。。
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=0;rg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
const int maxn=1e5+2;
int h[maxn];
int f[maxn],d[maxn];
int w[maxn];
int main(){
int n=gi(),ans1=1;
rep(i,1,n)h[i]=gi();
f[1]=1;
d[0]=-1e7;
d[1]=-h[1];
rep(i,2,n){
f[i]=lower_bound(d,d+i,-h[i])-d;
d[f[i]]=min(d[f[i]],-h[i]);
ans1=max(ans1,f[i]);
}
printf("%d\n",ans1);
int tot=1,r;
w[1]=h[1];
rep(i,2,n){
r=lower_bound(w+1,w+tot+1,h[i])-w;
if(r==tot+1)w[++tot]=h[i];
else w[r]=h[i];
}printf("%d\n",tot);
return 0;
}整数划分
如何把一个正整数 N（ N 长度<20）划分为 M（ M>1）个部分，使这 N 个部分的乘积最大。 N、 M 从键盘输入，输出最大值及一种划分方式
。。。乘积最大输出方案版。__int128能过，似乎unsigned long long也能过。。。
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<cstring>
#define Fname "separate"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef __int128 ll;
il int gi(){
rg int x=0;rg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
char str[22];
ll num[22][22];
ll f[22][22];
int g[22][22];
int ans[22];
il vd print(__int128 n){
if(n/10)print(n/10);
putchar(n%10+'0');
}
il vd work(){
scanf("%s",str+1);
int k=gi()-1,n=strlen(str+1);
rep(i,1,n)rep(j,1,n)num[i][j]=0;
rep(i,1,n)rep(j,i,n)num[i][j]=num[i][j-1]*10+str[j]-'0';
rep(i,1,n)rep(j,1,k)f[i][j]=0,g[i][j]=0;
rep(i,1,n)f[i][0]=num[1][i];
rep(i,1,n)rep(j,1,k)rep(l,1,i-1)if(f[i-l][j-1]*num[i-l+1][i]>f[i][j])f[i][j]=f[i-l][j-1]*num[i-l+1][i],g[i][j]=i-l;
if(f[n][k]!=0)print(f[n][k]),puts("");
else puts("0");
if(f[n][k]==0){
rep(i,1,k)putchar(str[i]),putchar(' ');
rep(i,k+1,n)putchar(str[i]);putchar(' ');
puts("");
return;
}
int K=k+1;
ans[n+1]=1;
rep(i,1,n)ans[i]=0;
rep(i,1,K-1)ans[g[n][k]+1]=1,n=g[n][k],--k;
int j=1;
rep(i,1,K){
do putchar(str[j++]);while(!ans[j]);
putchar(' ');
}
puts("");
}
int main(){
#ifdef xzz
freopen(Fname".in","r",stdin);
freopen(Fname".out","w",stdout);
#endif
int T=gi();
while(T--)work();
return 0;
}物品装箱问题
设有 n 种物品，记作 A1、 A2、 …、 An，对应于每个 Ai（ 1<=i<=n）都有一个重量 Awi和价值 Avi （重量和价值都为正整数）。另外，对应于每个 Ai，都有一件可代替它的“代用品”Bi，Bi 的重量和价值分别为 Bwi 和 Bvi。
本题的任务是：选择这 n 件物品或其代用品的一个子集装进背包，使总重量不超过给定重量 TOT，同时使总价值 VAL 最高。装填的第 I 步，要么装入 Ai，要么装入 Bi，要么 Ai和 Bi 都不装。
。。。分组背包极简版，两个一起更新就行了。。。
// It is made by XZZ
#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=0;rg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int f[10233];
int main(){
int n=gi(),m=gi(),w,v,W,V;
rep(i,1,n){
w=gi(),v=gi(),W=gi(),V=gi();
if(w>W)swap(w,W),swap(v,V);
drep(j,m,W)f[j]=max(f[j],max(f[j-w]+v,f[j-W]+V));
drep(j,W-1,w)f[j]=max(f[j],f[j-w]+v);
}
printf("%d\n",f[m]);
return 0;
}火车进站
codevs上似乎有？扯淡：尝试随机+线段树，失败。
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#define Fname "train"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
typedef long long ll;
il int gi(){
rg int x=0;rg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
struct train{int s,t;};
train s[101];
int data[201],n,m;
int val[810],lazy[810],tot;
il vd build(int x,int l,int r){
val[x]=m;
if(l==r)return;
build(ls,l,mid),build(rs,mid+1,r);
}
il vd Updata(int x,int l,int r,int&L,int&R){
if(lazy[x]&&(l^r)){
++lazy[ls],++lazy[rs];
--val[ls],--val[rs];
lazy[x]=0;
}
if(L<=l&&r<=R){++lazy[x],--val[x];return;}
if(L<=mid)Updata(ls,l,mid,L,R);
if(mid<R)Updata(rs,mid+1,r,L,R);
val[x]=min(val[ls],val[rs]);
}
int main(){
freopen(Fname".in","r",stdin);
freopen(Fname".out","w",stdout);
srand(time(NULL));
int ans=0;
bool flg=0;
n=gi(),m=gi();
rep(i,1,n)s[i].s=gi(),s[i].t=gi(),data[++tot]=s[i].s,data[++tot]=s[i].t;
sort(data+1,data+tot+1);
tot=unique(data+1,data+tot+1)-data-1;
rep(i,1,n)s[i].s=lower_bound(data+1,data+tot+1,s[i].s)-data,s[i].t=lower_bound(data+1,data+tot+1,s[i].t)-data;
rep(i,1,1e6){
random_shuffle(s+1,s+n+1);
build(1,1,tot);
flg=1;
rep(j,1,n){
Updata(1,1,tot,s[j].s,s[j].t);
if(val[1]<1){flg=0;ans=max(ans,j-1);break;}
}
if(flg){printf("%d\n",n);return 0;}
}printf("%d\n",ans);
return 0;
}正解？分情况dp
m=1:f[i]表示last=i
m=2:f[i][j]表示last=i,j
m=3:f[i][j][k]表示last=i,j,k
枚举再上一个是什么，并判断合法即可
// It is made by XZZ
#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=0;rg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int n;
struct heheda{int l,r;}s[111];
il bool cmp(const heheda&a,const heheda&b){return a.l-b.l?a.l<b.l:a.r<b.r;}
namespace m1{
int f[111];
il vd main(){
int ans=0;
rep(i,1,n){
f[i]=1;
rep(j,1,i-1)if(s[j].r<=s[i].l)f[i]=max(f[j]+1,f[i]);
ans=max(ans,f[i]);
}
printf("%d\n",ans);
}
}
namespace m2{
int f[111][111];
il vd main(){
int ans=0;
rep(i,1,n)rep(j,i+1,n)if(s[i].r<=s[j].r){
f[i][j]=2;
rep(k,1,i-1)if(s[k].r<=s[j].l)f[i][j]=max(f[k][i]+1,f[i][j]);
ans=max(ans,f[i][j]);
}
printf("%d\n",ans);
}
}
namespace m3{
int f[111][111][111];
il vd main(){
int ans=0;
rep(i,1,n)rep(j,i+1,n)if(s[i].r<=s[j].r)rep(k,j+1,n)if(s[j].r<=s[k].r){
f[i][j][k]=3;
rep(l,1,i-1)if(s[l].r<=s[k].l)f[i][j][k]=max(f[l][i][j]+1,f[i][j][k]);
ans=max(ans,f[i][j][k]);
}
printf("%d\n",ans);
}
}
int main(){
n=gi();int m=gi();
rep(i,1,n)s[i].l=gi(),s[i].r=gi();
sort(s+1,s+n+1,cmp);
if(m==1)m1::main();
if(m==2)m2::main();
if(m==3)m3::main();
return 0;
}