(D1T1) 能量项链 ((OK))
(D1T3) 作业调度方案 ((OK))
姑且算是完结撒花,(T4)有高精的部分就懒得写了.
(T1) 仅次于石子合并的区间(DP)模板题(???).设(f[i][j])表示合并区间([i,j])的最大得分,则枚举区间断点(k),(f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]*head[i]*tail[k](head[k+1])*tail[j])).
然后项链是个环,倍长数组从而断环为链是常规操作吧.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=205;
int head[N],tail[N],f[N][N];
int main(){
int n=read();
for(int i=1;i<=n;++i){
head[i]=read();
tail[i-1]=head[i];
}tail[n]=head[1];
for(int i=1;i<=n;++i)head[i+n]=head[i],tail[i+n]=tail[i];
for(int len=2;len<=n;++len){
for(int i=1;i+len-1<=n*2;++i){
int j=i+len-1;
for(int k=i;k<j;++k)
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);
}
}
int ans=0;for(int i=1;i<=n;++i)ans=max(ans,f[i][i+n-1]);
printf("%d
",ans);
return 0;
}
(T2) 有依赖性的(有主附件的)(01)背包模板题.设(f[i][j])表示考虑到了第(i)件主件物品,占用背包体积为(j)时的最大价值.转移的时候模型还是(01)背包的模型(因为不论是主件还是附件,都只有选或者不选两种情况),暴力枚举出所有的四种情况(只选主件,选主件和附件一,选主件和附件二,选主件和两个附件)即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=105;
int tot,ans,sum[N],f[N][32005];
struct node{int v,w,id;}e[N],g[N][3];
int main(){
int m=read(),n=read();
for(int i=1;i<=n;++i){
int a=read(),b=read(),c=read();
if(!c){
e[++tot].v=a;e[tot].w=b;e[i].id=tot;
}
if(c){
c=e[c].id;
g[c][++sum[c]].v=a;g[c][sum[c]].w=b;
}
}
for(int i=1;i<=tot;++i){
for(int j=m;j>=0;--j){
f[i][j]=f[i-1][j];
if(j>=e[i].v)f[i][j]=max(f[i][j],f[i-1][j-e[i].v]+e[i].v*e[i].w);
if(j>=e[i].v+g[i][1].v)f[i][j]=max(f[i][j],f[i-1][j-e[i].v-g[i][1].v]+e[i].v*e[i].w+g[i][1].v*g[i][1].w);
if(j>=e[i].v+g[i][2].v)f[i][j]=max(f[i][j],f[i-1][j-e[i].v-g[i][2].v]+e[i].v*e[i].w+g[i][2].v*g[i][2].w);
if(j>=e[i].v+g[i][1].v+g[i][2].v)f[i][j]=max(f[i][j],f[i-1][j-e[i].v-g[i][1].v-g[i][2].v]+e[i].v*e[i].w+g[i][1].v*g[i][1].w+g[i][2].v*g[i][2].w);
}
}
printf("%d
",f[tot][m]);
return 0;
}
(T3)根据题意来模拟即可.一边写代码的时候就一边做了注释,这里懒得讲了.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=21;
const int M=405;
int ord[M],bel[N][N],tim[N][N],Has[N],End[N],maxn[N],bj[N][100005];
int main(){
int m=read(),n=read();
for(int i=1;i<=n*m;++i)ord[i]=read();//第i个顺序安排哪个工件
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)bel[i][j]=read();//第i个工件的第j道工序在哪个机器上完成
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)tim[i][j]=read();//第i个工件的第j道工序所需时间
int ans=0;
for(int i=1;i<=n*m;++i){
int now=ord[i];//当前安排哪个工件
int has=++Has[now];//该工件当前到第几个工序了
int jqh=bel[now][has];//要在哪个机器上完成
int sum=0,BJ=0;
for(int j=max(0,End[now])+1;j<=maxn[jqh];++j){//能插之前的空就插之前的空
if(!bj[jqh][j])++sum;
else sum=0;
if(sum>=tim[now][has]){
for(int k=j;k>=j+1-tim[now][has];--k)bj[jqh][k]=1;
End[now]=j;BJ=1;break;
}
}
if(!BJ){//否则就要在这个机器后面新开一段时间
int st=max(maxn[jqh],End[now]);
for(int j=st+1;j<=st+tim[now][has];++j)bj[jqh][j]=1;
maxn[jqh]=st+tim[now][has];End[now]=maxn[jqh];ans=max(ans,maxn[jqh]);
}
}
printf("%d
",ans);
return 0;
}
(T4)设(f[i][j])表示从右往左第(i)位填数字(j)时的方案数,则(f[i][j]=sum_{x=j+1}^{2^k-1}f[i-1][x]),如果每次转移的时候暴力枚举([j+1,2^k-1])显然会超时,所以要前缀和优化,即每次更新(f[i-1][j])的同时维护一下(sum[i-1][j]=sum[i-1][j-1]+f[i-1][j]),那么转移(f[i][j])的时候直接(O(1))地(f[i][j]=sum[i-1][2^k-1]-sum[i-1][j])即可.
反正我交上去获得了(50)分,我就默认剩下(50)分都是高精了啊.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=15005;
int k,w,bj;
int Base[10];
ll f[N][520],sum[N][520];
int main(){
Base[0]=1;for(int i=1;i<=9;++i)Base[i]=Base[i-1]<<1;
k=read();w=read();int n=w/k;if(w%k)bj=1,++n;
for(int j=0;j<=Base[k]-1;++j)f[1][j]=1,sum[1][j]=sum[1][j-1]+f[1][j];
for(int i=2;i<=n;++i){
for(int j=1;j<=Base[k]-1;++j){
f[i][j]=sum[i-1][Base[k]-1]-sum[i-1][j];
sum[i][j]=sum[i][j-1]+f[i][j];
}
}
if(bj){
ll ans=0;
for(int i=2;i<n;++i)
for(int j=1;j<=Base[k]-1;++j)ans+=f[i][j];
for(int j=1;j<=Base[(Base[k]%w)-1];++j)ans+=f[n][j];
printf("%lld
",ans);return 0;
}
ll ans=0;
for(int i=2;i<=n;++i)
for(int j=1;j<=Base[k]-1;++j)ans+=f[i][j];
printf("%lld
",ans);
return 0;
}