线性DP例题
Axell
2月 06, 2019
线性DP例题
拍照排列P263
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int k,a[10],n[10];
void solve(){
memset(n,0,sizeof n);
for (int i=1;i<=k;++i) scanf("%d",&n[i]);
ll f[n[1]+1][n[2]+1][n[3]+1][n[4]+1][n[5]+1];
memset(f,0,sizeof f); f[0][0][0][0][0]=1;
for (a[1]=0;a[1]<=n[1];++a[1])
for (a[2]=0;a[2]<=n[2];++a[2])
for (a[3]=0;a[3]<=n[3];++a[3])
for (a[4]=0;a[4]<=n[4];++a[4])
for (a[5]=0;a[5]<=n[5];++a[5]){
ll tmp=f[a[1]][a[2]][a[3]][a[4]][a[5]];
if (a[1]<n[1]) f[a[1]+1][a[2]][a[3]][a[4]][a[5]]+=tmp;
if (a[2]<n[2] && a[2]<a[1]) f[a[1]][a[2]+1][a[3]][a[4]][a[5]]+=tmp;
if (a[3]<n[3] && a[3]<a[2]) f[a[1]][a[2]][a[3]+1][a[4]][a[5]]+=tmp;
if (a[4]<n[4] && a[4]<a[3]) f[a[1]][a[2]][a[3]][a[4]+1][a[5]]+=tmp;
if (a[5]<n[5] && a[5]<a[4]) f[a[1]][a[2]][a[3]][a[4]][a[5]+1]+=tmp;
}
cout<<f[n[1]][n[2]][n[3]][n[4]][n[5]]<<endl;
}
int main(){
while (scanf("%d",&k)){
if (k==0) break;
solve();
}
return 0;
} LCISP264
#include <bits/stdc++.h>
using namespace std;
int l,a[3005],b[3005],f[3005][3005],g[3005][3005],mt,ans;
int main(){
cin>>l;
for (int i=1;i<=l;++i) scanf("%d",&a[i]);
for (int i=1;i<=l;++i) scanf("%d",&b[i]);
a[0]=b[0]=-1e9;
for (int i=1;i<=l;++i){
mt=0;
for (int j=1;j<=l;++j){
if (a[i]==b[j]) f[i][j]=mt+1;
else f[i][j]=f[i-1][j];
if (b[j]<a[i]) mt=max(mt,f[i-1][j]);
ans=max(ans,f[i][j]);
}
}
cout<<ans<<endl;
return 0;
}移动服务P267
#include <bits/stdc++.h>
using namespace std;
int f[2][205][205],c[205][205],p[1005],l,n;
int main(){
cin>>l>>n;
for (int i=1;i<=l;++i){
for (int j=1;j<=l;++j){
scanf("%d",&c[i][j]);
}
}
for (int i=1;i<=n;++i) scanf("%d",&p[i]);
p[0]=3;
memset(f,0x3f,sizeof(f));
f[0][1][2]=0;
for (int i=0;i<=n;++i){
for (int j=1;j<=l;++j){
for (int k=1;k<=l;++k){
if (p[i+1]!=j && p[i+1]!=k && j!=k) f[1][j][k]=min(f[1][j][k],f[0][j][k]+c[p[i]][p[i+1]]);
if (p[i+1]!=p[i] && p[i]!=k && p[i+1]!=k) f[1][p[i]][k]=min(f[1][p[i]][k],f[0][j][k]+c[j][p[i+1]]);
if (p[i]!=p[i+1] && p[i]!=j && p[i+1]!=j) f[1][j][p[i]]=min(f[1][j][p[i]],f[0][j][k]+c[k][p[i+1]]);
}
}
for (int j=1;j<=l;++j){
for (int k=1;k<=l;++k){
f[0][j][k]=f[1][j][k];
f[1][j][k]=1e9;
}
}
}
int ans=1e9;
for (int i=1;i<=l;++i){
for (int j=1;j<=l;++j){
ans=min(ans,f[0][i][j]);
}
}
cout<<ans<<endl;
}构造单调序列P265
#include <bits/stdc++.h>
using namespace std;
int a[2005],b[2005],f[2005],g[2005],n,m;
int main(){
cin>>n;
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
for (int i=1;i<=n;++i) b[i]=a[i];
sort(b+1,b+n+1);
m=unique(b+1,b+n+1)-(b+1);
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j){
f[j]=g[j]+abs(b[j]-a[i]);
}
g[1]=f[1];
for (int j=2;j<=m;++j){
g[j]=min(g[j-1],f[j]);
}
}
cout<<g[m]<<endl;
return 0;
}I-country P269
#include <bits/stdc++.h>
using namespace std;
int f[16][226][16][16][2][2],n,m,t,a[16][16],b[16][16],k;
struct node{
int i,j,l,r,x,y;
}ans[16][226][16][16][2][2],as;
void pr(node as){
if (!as.i) return;
pr(ans[as.i][as.j][as.l][as.r][as.x][as.y]);
for (int i=as.l;i<=as.r;++i) printf("%d %d\n",as.i,i);
}
int main(){
cin>>n>>m>>t;
for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) scanf("%d",&a[i][j]);
for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) b[i][j]=b[i][j-1]+a[i][j];
for (int i=1;i<=n;++i){
for (int j=1;j<=t;++j){
for (int l=1;l<=m;++l){
for (int r=l;r<=m;++r){
if ((k=r-l+1)>j) break;
int tmp=b[i][r]-b[i][l-1];
if (k==j){
for (int x=0;x<=1;++x) for (int y=0;y<=1;++y) f[i][j][l][r][x][y]=tmp;
}else{
for (int p=l;p<=r;++p){
for (int q=p;q<=r;++q){
if (f[i][j][l][r][1][0]<f[i-1][j-k][p][q][1][0]){
f[i][j][l][r][1][0]=f[i-1][j-k][p][q][1][0];
ans[i][j][l][r][1][0]={i-1,j-k,p,q,1,0};
}
}
}
for (int p=1;p<=l;++p){
for (int q=l;q<=r;++q){
for (int x=0;x<=1;++x){
if (f[i][j][l][r][0][0]<f[i-1][j-k][p][q][x][0]){
f[i][j][l][r][0][0]=f[i-1][j-k][p][q][x][0];
ans[i][j][l][r][0][0]={i-1,j-k,p,q,x,0};
}
}
}
}
for (int p=l;p<=r;++p){
for (int q=r;q<=m;++q){
for (int y=0;y<=1;++y){
if (f[i][j][l][r][1][1]<f[i-1][j-k][p][q][1][y]){
f[i][j][l][r][1][1]=f[i-1][j-k][p][q][1][y];
ans[i][j][l][r][1][1]={i-1,j-k,p,q,1,y};
}
}
}
}
for (int p=1;p<=l;++p){
for (int q=r;q<=m;++q){
for (int x=0;x<=1;++x){
for (int y=0;y<=1;++y){
if (f[i][j][l][r][0][1]<f[i-1][j-k][p][q][x][y]){
f[i][j][l][r][0][1]=f[i-1][j-k][p][q][x][y];
ans[i][j][l][r][0][1]={i-1,j-k,p,q,x,y};
}
}
}
}
}
for (int x=0;x<=1;++x) for (int y=0;y<=1;++y) f[i][j][l][r][x][y]+=tmp;
}
}
}
}
}
int mtans=0;
for (int i=1;i<=n;++i){
for (int l=1;l<=m;++l){
for (int r=l;r<=m;++r){
for (int x=0;x<=1;++x){
for (int y=0;y<=1;++y){
if (mtans<f[i][t][l][r][x][y]){
mtans=f[i][t][l][r][x][y];
as={i,t,l,r,x,y};
}
}
}
}
}
}
printf("Oil : %d\n",mtans);
pr(as);
return 0;
}cookies P271
#include <bits/stdc++.h>
using namespace std;
struct node{
int id,v,cnt;
}g[35];
bool cmp(node x,node y){return x.v>y.v;}
bool cmpp(node x,node y){return x.id<y.id;}
struct sta{
int i,j;
}ans[35][5005];
void pr(int n,int m){
if (!n) return;
sta now=ans[n][m];
pr(now.i,now.j);
if (now.i==n){
for (int i=1;i<=n;++i) g[i].cnt++;
}else{
for (int i=now.i+1;i<=n;++i) g[i].cnt=1;
}
}
int n,m,f[35][5005],s[35];
int main(){
cin>>n>>m;
for (int i=1;i<=n;++i) scanf("%d",&g[i].v),g[i].id=i;
sort(g+1,g+n+1,cmp);
memset(f,0x3f,sizeof f);
f[0][0]=0;
for (int i=1;i<=n;++i){
s[i]=s[i-1]+g[i].v;
for (int j=i;j<=m;++j){
f[i][j]=f[i][j-i];
ans[i][j]={i,j-i};
for (int k=0;k<=i-1;++k){
if (f[i][j]>f[k][j-i+k]+k*(s[i]-s[k])){
f[i][j]=f[k][j-i+k]+k*(s[i]-s[k]);
ans[i][j]={k,j-i+k};
}
}
}
}
cout<<f[n][m]<<endl;
pr(n,m);
sort(g+1,g+n+1,cmpp);
for (int i=1;i<=n;++i) printf("%d ",g[i].cnt);
return 0;
}
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/91/
