dp 太差了，爆零 首先是乱蒙 if((dp[i][k]+dp[k+1][j]+(a[i][k]*a[k+1][j])%100)<dp[i][j])
其次 尝试用i,j,k做区间，应该用k代表区间长度
最后初始化不对
#include<iostream> #include<string.h> #include<math.h> #include<stdio.h> #include<algorithm> using namespace std; int dp[105][105]; int a[105][105]; int t; int n; void clean() { memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); } int main() { //freopen("wish.in","r",stdin); //freopen("wish.out","w",stdout); int i,j,k,l; cin>>t; for(l=1;l<=t;l++) { clean(); cin>>n; for(i=1;i<=n;i++) { cin>>a[i][i]; } if(n==2) {cout<<a[1][1]*a[2][2]<<endl;continue;} for(i=1;i<n;i++) { for(j=i+1;j<=n;j++) { for(k=i;k<=j;k++) { a[i][j]=a[k][k]+a[i][j]; //a[i][j]=a[i][j]%100; } } } dp[1][2]=a[1][1]*a[2][2]; for(k=n-1;k>=1;k--) for(i=1;i<=k;i++) for(j=k+1;j<=n;j++) { if((dp[i][k]+dp[k+1][j]+(a[i][k]*a[k+1][j])%100)>dp[i][j]) { //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; dp[i][j]=dp[i][k]+dp[k+1][j]+a[i][k]*a[k+1][j]; a[i][j]=a[i][k]+a[k+1][j]; } } cout<<dp[1][n]<<endl; } return 0; }
与我的方法较接近的方法
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,cnt,t; ll dp[109][109]; ll then[109][109],a[109]; int main() { freopen("wish.in","r",stdin); freopen("wish.out","w",stdout); cin>>t; while(t--)//要初始化！！！ { memset(a,0,sizeof(a)); memset(then,0,sizeof(then)); cin>>n; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) { dp[i][j]=99999999999999999; } for(int i=1;i<=n;i++) { cin>>a[i]; then[i][i]=a[i]; } for(int i=1;i<n;i++) { dp[i][i+1]=a[i]*a[i+1];//此处需要注意 then[i][i+1]=(a[i]+a[i+1])%100; } for(int i=1;i<=n;i++) dp[i][i]=0;//从i到自己不用费力 for(int len=3;len<=n;len++)//区间长度 { for(int i=1;i<=n;i++)//区间起点 { int j=i+len-1; if(j>n)break; for(int k=i;k<j;k++)//k前面的乘起来再乘后面的 { dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+then[i][k]*then[k+1][j]);//注意此处不能mod then[i][j]=(then[i][k]+then[k+1][j])%100;//注意此处必须mod，因为g下面的已经mod了m（i,j），此预处理只有m（i，i+1）； } } } cout<<dp[1][n]<<endl; } return 0; }
更简单的方法---合并石子
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #define ll long long #define mod 100 #define cl(x) memset(x,0,sizeof x) #define pl(x) memset(x,9999999,sizeof x) using namespace std; const int maxn=1000+5; ll f[maxn][maxn],a[maxn],m[maxn][maxn]; ll n,t; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { freopen("wish.in","r",stdin); freopen("wish.out","w",stdout); t=read(); while(t--) { pl(f);cl(m);cl(a); n=read(); for(int i=1;i<=n;i++) { int k=read();a[i]=k+a[i-1];f[i][i]=0; } for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) m[i][j]=(a[j]-a[i-1])%mod;//即我a【i]【j】； for(int i=2;i<=n;i++)//区间大小 for(int j=1;j<=n-i+1;j++) { int k=j+i-1; for(int h=j;h<k;h++) f[j][k]=min(f[j][k],f[j][h]+f[h+1][k]+m[j][h]*m[h+1][k]); } cout<<f[1][n]<<endl; } return 0; }
订正
#include<iostream> #include<string.h> #include<math.h> #include<stdio.h> #include<algorithm> using namespace std; int dp[105][105]; int m[105][105]; int a[105]; int t; int n; void clean() { memset(dp,0x7f,sizeof(dp)); memset(a,0,sizeof(a)); } int main() { //freopen("wish.in","r",stdin); //freopen("wish.out","w",stdout); int i,j,k,l; cin>>t; for(l=1;l<=t;l++) { clean(); cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; m[i][i]=a[i]; dp[i][i]=0; } for(i=1;i<=n-1;i++) { dp[i][i+1]=a[i]*a[i+1]; m[i][i+1]=(a[i]+a[i+1])%100; } for(i=2;i<=n;i++)//cnt for(j=1;j<=n-i+1;j++)//strat { int h=i+j-1; for(k=j;k<h;k++) { dp[j][h]=min(dp[j][h],dp[j][k]+dp[k+1][h]+m[j][k]*m[k+1][h]); m[j][h]=(m[j][k]+m[k+1][h])%100; } } cout<<dp[1][n]<<endl; } return 0; }