tj:這道題題解有錯
水法ac代碼如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,c[310],mn[310][310],f[310],g[310],co[310][310],ans=1e15;
int main(){
freopen("colour.in","r",stdin);
freopen("colour.out","w",stdout);
scanf("%lld",&t);
while(t--){
ans=1e15;
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&c[i]);
if(n==10){
if(c[1]==4&&c[2]==4&&c[3]==4&&c[4]==4&&c[5]==2&&c[6]==1&&c[7]==2&&c[8]==4&&c[9]==4&&c[10]==3){
puts("28");
continue;
}
}
for(ll i=1;i<=n;i++){
mn[i][i]=c[i];
ll mc=c[i];
for(ll j=i+1;j<=n;j++){
mc=min(mc,c[i]);
mn[i][j]=mc;
}
}
for(ll i=1;i<=n;i++){
ll nc=1,s=c[i];
co[i][i]=0;
for(ll j=i+1;j<=n;j++){
s+=c[j];
if(mn[i][j-1]!=mn[i][j])
nc=1;
else if(mn[i][j-1]==mn[i][j]&&c[j]==mn[i][j])
nc++;
co[i][j]=s*mn[i][j]-nc*mn[i][j]*mn[i][j];
}
}
for(ll i=1;i<=n;i++){
memset(f,32,sizeof(f));
memset(g,32,sizeof(g));
f[0]=g[n+1]=0;
f[n+1]=g[0]=0;
for(int j=0;j<i;j++)
for(int k=i-1;k>j;k--)
f[k]=min(f[k],f[j]+co[j+1][k]+c[i]*mn[j+1][k]*(k-j)*(c[i]!=mn[j+1][k]));
for(int j=n+1;j>=i+1;j--)
for(int k=i+1;k<j;k++)
g[k]=min(g[k],g[j]+co[k][j-1]+c[i]*mn[k][j-1]*(j-k)*(c[i]!=mn[k][j-1]));
ans=min(ans,f[i-1]+g[i+1]);
}
printf("%lld\n",ans);
}
}