水表

水表

关注
发信
关注(28)粉丝(399)

9.15 DP合集水表

9.15 DP合集水表

显然难了一些啊。

凸多边形的三角剖分

瞄了一眼题解。

和蛤蛤的烦恼一样，裸的区间dp。

设f[i][j]表示i~j的点三角剖分最小代价。

显然\(f[i][i+1]=0,f[i][i+2]=w[i]*w[i+1]*w[i+2]\)

然后枚举i,j和哪个点剖。

\[f[l][r]=min(f[l][r],f[l][i]+f[i][r]+w[l]*w[r]*w[i]) (l<i<r)
\]

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define Fname "division"

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;

}

ll w[101],f[101][101];

int main(){

    #ifdef xzz

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

    #endif

    int n=gi(),r;

    rep(i,1,n)w[i]=w[i+n]=gi();

    n*=2;

    rep(i,3,n)f[i-2][i]=w[i-2]*w[i-1]*w[i];

    rep(siz,4,n/2)drep(l,n-siz+1,1){

	r=l+siz-1;

	f[l][r]=1e18;

	rep(i,l+1,r-1)f[l][r]=min(f[l][r],f[l][i]+f[i][r]+w[l]*w[r]*w[i]);

    }

    n/=2;

    ll ans=2e18;

    rep(i,1,n)ans=min(ans,f[i][i+n-1]);

    printf("%lld\n",ans);

    return 0;

}

求最长公共子序列

SBT，切掉

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#include<cstring>

#define Fname "lcs"

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[5002],b[5002];

int f[5002][5002];

int main(){

    #ifdef xzz

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

    #endif

    scanf("%s%s",a+1,b+1);

    int lena=strlen(a+1)-1,lenb=strlen(b+1)-1;

    rep(i,1,lena)rep(j,1,lenb)

	if(a[i]==b[j])f[i][j]=f[i-1][j-1]+1;

	else f[i][j]=max(f[i-1][j],f[i][j-1]);

    printf("%d\n",f[lena][lenb]);

    return 0;

}

卡车更新问题

设f[i][j]表示第i天，上次更新是j就好了

主要难在输出方案，恶心细节多

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define Fname "truck"

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;

}

#define db double

db R[23],U[23],C[23];

db f[23][23];

int g[23][23];

il vd Min(db&a,int&b,db c,int d){if(c>a)a=c,b=d;}

//f[i][j] 到第i天，上次更新是第j天的总回收额max

bool yes[23];

int main(){

    #ifdef xzz

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

    #endif

    int n=gi(),k=gi();

    rep(i,0,k)scanf("%lf",&R[i]);

    rep(i,0,k)scanf("%lf",&U[i]);

    rep(i,0,k)scanf("%lf",&C[i]);

    rep(i,1,n+1)rep(j,0,k)f[i][j]=-233333.33;

    f[1][0]=R[0]-U[0];

    rep(i,1,n-1)rep(j,0,i-1){

	if(i-j<k)Min(f[i+1][j],g[i+1][j],f[i][j]+R[i-j]-U[i-j],j);

	Min(f[i+1][i],g[i+1][i],f[i][j]+R[0]-U[0]-C[i-j],j);

    }

    int ans=n-1;

    rep(i,n-k,n-2)if(f[n][i]>f[n][ans])ans=i;

    printf("%.1f\n",f[n][ans]);

    int x=n,y=ans;

    while(x){

	if(y==x-1)yes[x]=1;

        y=g[x][y],--x;

    }x=n,y=ans;

    printf("%d 0 %.1f\n",1,R[0]-U[0]);

    y=1;

    rep(i,2,n){

	if(yes[i])printf("%d 1 %.1f\n",i,R[0]-U[0]-C[y]),y=1;

	else printf("%d 0 %.1f\n",i,R[y]-U[y]),++y;

    }

    return 0;

}

选课

裸的树形背包但要输出方案。GG

不会

为了挽尊，特写spj一个。。。

#include<bits/stdc++.h>

using namespace std;

int main(int argc,char *argv[])

{

    FILE *in,*out,*ans,*score,*report;

    out=fopen(argv[2],"r");

    ans=fopen(argv[3],"r");

    score=fopen(argv[5],"w");

    report=fopen(argv[6],"w");

    int a=-2333,b=-6666;

    fscanf(out,"%d",&a);

    fscanf(ans,"%d",&b);

    if(a==b){

	while(fscanf(out,"%d",&a)==1||fscanf(ans,"%d",&b)==1)

	    if(a!=b){fprintf(score,"3"),fprintf(report,"方案错了。。。3分");return 0;}

	fprintf(score,"10"),fprintf(report,"泥太有才了！");

    }

    else fprintf(score,"0"),fprintf(report,"答案都错了。。。期望%d但输出%d",b,a);

}

没方案或方案错了就会得到3分233

贴一下没方案的代码

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define Fname "course"

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=520,maxm=maxn;

int m,n,w[maxn],fir[maxn],dis[maxm],nxt[maxm],id;

il vd add(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}

int f[maxn][maxn];

il vd dp(int x,int M){

    if(M==0)return;

    erep(i,x){

	rep(j,1,M-1)f[dis[i]][j]=f[x][j];

	dp(dis[i],M-1);

	drep(j,M,1)f[x][j]=max(f[x][j],f[dis[i]][j-1]+w[dis[i]]);

    }

}

int main(){

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

    m=gi(),n=gi();

    rep(i,1,m)add(gi(),i),w[i]=gi();

    dp(0,n);

    printf("%d\n",f[0][n]);

    return 0;

}

蛤蛤的烦恼

利用了凸多边形的性质。

然而窝不会证。

f[l][r]表示从l开始遍历l~r的最小代价。

g[l][r]表示从r开始遍历l~r的最小代价。

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#include<cmath>

#define Fname "frog"

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;

}

#define db double

#define maxn 721

db x[maxn],y[maxn];

db f[maxn][maxn],g[maxn][maxn];

il db dist(int a,int b){return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));}

int main(){

    #ifdef xzz

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

    #endif

    int n=gi(),r;

    rep(i,1,n)scanf("%lf%lf",&x[i],&y[i]);

    rep(siz,2,n)drep(l,n-siz+1,1){

	r=l+siz-1;

	f[l][r]=min(f[l+1][r]+dist(l,l+1),g[l+1][r]+dist(l,r));

	g[l][r]=min(g[l][r-1]+dist(r-1,r),f[l][r-1]+dist(l,r));

    }

    printf("%.3f\n",f[1][n]);

    return 0;

}

警卫安排

灰常经典乐，以前早写过类似的辣

f[i]表示父亲染i，g表示i染i，h表示i的儿子染i

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define Fname "security"

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=722;

int n,w[maxn];

int fir[maxn],dis[maxn],nxt[maxn],id;

il vd add(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}

int f[maxn],g[maxn],h[maxn];

//f父亲or自己染自己，g自己染自己，h儿子or自己染自己

il vd dp(int x){

    f[x]=0,g[x]=w[x],h[x]=1e9;

    int Sum=0;

    erep(i,x){

	dp(dis[i]);

	Sum+=h[dis[i]];

	g[x]+=f[dis[i]];

	f[x]+=h[dis[i]];

    }

    erep(i,x)h[x]=min(h[x],Sum-h[dis[i]]+g[dis[i]]);

    h[x]=min(h[x],g[x]);

    f[x]=min(f[x],g[x]);

}

int isson[maxn];

int main(){

    #ifdef xzz

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

    #endif

    n=gi();

    int son,s,a,root;

    rep(i,1,n){

	s=gi();

	w[s]=gi();

	son=gi();

	while(son--)a=gi(),isson[a]=1,add(s,a);

    }

    rep(i,1,n)if(!isson[i])root=i;

    dp(root);

    printf("%d\n",min(g[root],h[root]));

    return 0;

}

最长上升子序列

SBT。k前去掉比a[k]打的，k后去掉比a[k]小的，显然答案不变而且能取到k

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define Fname "lis"

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=2e5+2;

int d[maxn],a[maxn];

int main(){

#ifdef xzz

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

#endif

    int s,n=gi(),k=gi(),maxf=0;

    rep(i,1,n)a[i]=gi();

    d[0]=-2e9;

    rep(i,1,n)d[i]=2e9;

    rep(i,1,n){

	if((i<k&&a[i]>=a[k])||(i>k&&a[i]<=a[k]))continue;

	s=lower_bound(d,d+maxf+1,a[i])-d;

	//f[i]=s

	d[s]=min(d[s],a[i]);maxf=max(maxf,s);

    }

    printf("%d\n",maxf);

    return 0;

}

最短回文串

同编辑距离。稍作改动就行

f[l][r]表示[l,r]变成回文串最少插几个字符

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define Fname "palindrome"

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 s[5010];

short f[5010][5010];

int main(){

#ifdef xzz

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

#endif

    int n=gi(),r;

    scanf("%s",s+1);

    rep(siz,2,n)drep(l,n-siz+1,1){

	r=l+siz-1;

	if(s[l]==s[r])f[l][r]=f[l+1][r-1];

	else f[l][r]=min(f[l+1][r],f[l][r-1])+1;

    }printf("%d\n",f[1][n]);

    return 0;

}

水表搞定了！

备份，密码同博客密码

05-11 22:15
Powered by LMLPHP ©2024 水表 0.048270