题解在代码中
石子合并[loj 10147]
/* dp[i][j]=max or min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]) i<=k<j */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; inline int read() { int f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } int a[401],n,dp_minn[401][401],dp_maxn[401][401],sum[401]; int main() { memset(dp_minn,127,sizeof(dp_minn)); n=read(); for(int i=1;i<=n;i++) { dp_minn[i][i]=dp_minn[i+n][i+n]=0; a[i]=read(),a[i+n]=a[i]; } for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i]; for(int t=2;t<=n;t++) for(int i=1;i<=2*n&&i+t-1<=2*n;i++) { int j=i+t-1; for(int k=i;k<j;k++) { dp_maxn[i][j]=max(dp_maxn[i][j],dp_maxn[i][k]+dp_maxn[k+1][j]+sum[j]-sum[i-1]); dp_minn[i][j]=min(dp_minn[i][j],dp_minn[i][k]+dp_minn[k+1][j]+sum[j]-sum[i-1]); }//cout<<i<<" "<<j<<" "<<dp_minn[i][j]<<endl; } int maxn=0,minn=2<<30-1; for(int i=1;i<=n;i++) maxn=max(maxn,dp_maxn[i][i+n-1]),minn=min(minn,dp_minn[i][i+n-1]); cout<<minn<<endl<<maxn; }
能量项链[loj 10148]
/* 为了好想 记录每一的head和tail so dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+head[i]*tail[k]*tail[j]) i<=k<j */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; inline long long read() { long long f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } long long dp[201][201],a[201],h[201],t[201]; int main() { long long n=read(); for(long long i=1;i<=n;i++) a[i]=read(),a[i+n]=a[i]; for(long long i=1;i<2*n;i++) h[i]=a[i],t[i]=a[i+1]; // for(int i=1;i<2*n;i++) cout<<h[i]<<" "<<t[i]<<endl; for(long long tt=1;tt<n;tt++) for(long long i=1;i<=2*n&&i+tt<=2*n;i++) { long long j=i+tt; // cout<<i<<" "<<j<<endl; for(long long k=i;k<j;k++) dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+h[i]*t[k]*t[j]); } long long maxn=0; for(long long i=1;i<=n;i++) maxn=max(maxn,dp[i][i+n-1]); cout<<maxn; } /* 7 23 17 212 113 71 301 33 31182687 */
凸多边形的划分[loj 10149]
/* 高精度或__int128 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]) dp[i][j][0]存位数 其他四个数一个int */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; inline long long read() { long long f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return ans*f; } long long n,a[51]; long long dp[110][110][110]; long long s1[110],s2[110],s3[110]; void print() { cout<<dp[1][n][dp[1][n][0]]; for(long long i=dp[1][n][0]-1;i>=1;i--) { cout<<dp[1][n][i]/1000; cout<<dp[1][n][i]/100%10; cout<<dp[1][n][i]/10%10; cout<<dp[1][n][i]%10; } } void mark(long long c[]) { for(long long i=1;i<=c[0];i++) { c[i+1]+=c[i]/10000; c[i]%=10000; } while(c[c[0]+1]!=0) { c[0]++; c[c[0]+1]=c[c[0]]/10000; c[c[0]]%=10000; } } void mul(long long a1,long long a2,long long a3,long long c[]) { c[0]=c[1]=1; for(long long i=1;i<=c[0];i++) c[i]*=a1; mark(c); for(long long i=1;i<=c[0];i++) c[i]*=a2; mark(c); for(long long i=1;i<=c[0];i++) c[i]*=a3; mark(c); } void add(long long a[],long long b[],long long c[]) { if(a[0]>b[0]) c[0]=a[0]; else c[0]=b[0]; for(long long i=1;i<=c[0];i++) c[i]=a[i]+b[i]; mark(c); } long long compare(long long a[],long long b[]) { if(a[0]>b[0]) return 1; if(a[0]<b[0]) return 0; for(long long i=a[0];i>=1;i--) { if(a[i]<b[i]) return 0; else if(a[i]>b[i]) return 1; } return 0; } int main() { n=read(); for(long long i=1;i<=n;i++) a[i]=read(); for(long long t=2;t<=n-1;t++) { for(long long i=1;i+t<=n;i++) { long long j=i+t; dp[i][j][0]=60; for(long long k=i+1;k<=j-1;k++) { memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); memset(s3,0,sizeof(s3)); mul(a[i],a[k],a[j],s1); add(dp[i][k],dp[k][j],s2); add(s1,s2,s3); if(compare(dp[i][j],s3)) memcpy(dp[i][j],s3,sizeof(s3)); } } } print(); }
括号配对[loj 10150]
/* dp[i][j]表示在[i,j]中至少需要添加的数量 1. (i==[ j==] ) or(i==( j==)) dp[i][j]=min(dp[i][j],dp[i+1][j-1] 2. i==( or i==[ dp[i][j]=min(dp[i][j],dp[i+1][j]) 3. j==) or j==] dp[i][j]=min(dp[i][j],dp[i][j-1]) 4. dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]) (i<=k<j) 初始化时dp[i][j]=inf (i<=j) dp[i][i]=1;(1<=i<=n) 想一想为什么 */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; inline int read() { int f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } char str[102]; int a[102]; int dp[110][110],inf=2<<30-1; int main() { // memset(dp,127,sizeof(dp)); scanf("%s",str+1); int len=strlen(str+1); for(int i=1;i<=len;i++) for(int j=i;j<=len;j++) dp[i][j]=inf; for(int i=1;i<=len;i++) { dp[i][i]=1; if(str[i]=='(') a[i]=1; if(str[i]==')') a[i]=2; if(str[i]=='[') a[i]=3; if(str[i]==']') a[i]=4; } for(int t=1;t<len;t++) { for(int i=1;i+t<=len;i++) { int j=i+t; if((a[i]==1&&a[j]==2)||(a[i]==3&&a[j]==4)) dp[i][j]=min(dp[i][j],dp[i+1][j-1]); if(a[i]==1||a[i]==3) dp[i][j]=min(dp[i][j],dp[i+1][j]+1); if(a[j]==2||a[j]==4) dp[i][j]=min(dp[i][j],dp[i][j-1]+1); for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); // cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; } } cout<<dp[1][len]; }
分离与合体[loj 10151]
/* dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+(a[i]+a[j])*a[k]) i<=k<j 用last记录 bfs保证了一分为二，二分为四的输出 */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; inline int read() { int f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } int n,a[301],dp[301][301],last[301][301]; void bfs() { queue< pair <int,int > > que; que.push(make_pair(1,n)); while(!que.empty()) { pair<int,int> s=que.front(); que.pop(); if(s.first==s.second) continue; cout<<last[s.first][s.second]<<" "; que.push(make_pair(s.first,last[s.first][s.second])); que.push(make_pair(last[s.first][s.second]+1,s.second)); } } int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int t=1;t<n;t++) for(int i=1;i+t<=n;i++) { int j=i+t; for(int k=j-1;k>=i;k--) { int t=dp[i][k]+dp[k+1][j]+(a[i]+a[j])*a[k]; if(t>=dp[i][j]) { dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+(a[i]+a[j])*a[k]); last[i][j]=k; } } } cout<<dp[1][n]<<endl; bfs(); return 0; }
矩阵取数游戏[loj 10152]
/* 一行一行处理 dp[i][j]表示变到 i,j时的最大分数 dp[i][j]=max(dp[i][j],dp[i-1][j]*a[i-1]^pow(2,n+i-j-1),dp[i][j+1]*a[j+1]^pow(2,n+i-j-1)) */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; inline long long read() { long long f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } __int128 dp[101][101],ans,sry[101]; long long n,m,a[101]; void print(__int128 x) { if(x==0) return; else if(x!=0) print(x/10); putchar(x%10+'0'); } int main() { sry[0]=1; for(int i=1;i<=100;i++) sry[i]=sry[i-1]*2; n=read(),m=read(); for(long long i=1;i<=n;i++) { for(long long j=1;j<=m;j++) a[j]=read(); memset(dp,0,sizeof(dp)); for(long long i=1;i<=m;i++) for(long long j=m;j>=i;j--) dp[i][j]=max(dp[i-1][j]+a[i-1]*sry[m-j+i-1],dp[i][j+1]+a[j+1]*sry[m-j+i-1]); __int128 maxn=-1; for(long long i=1;i<=m;i++) maxn=max(maxn,dp[i][i]+a[i]*sry[m]); ans+=maxn; } if(ans==0) { cout<<0;return 0;} print(ans); }