jzoj5925
2024-09-26 08:37:39
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);
}
}
最新文章
- Mac下修改环境变量
- isPowerOfTwo
- windows中 dll 的解读
- VS编译的QT程序发布时产生的AppCrash问题
- 用c#写一个json的万能解析器
- Bitmap 多语言实现及应用
- Java面向对象知识点精华
- POJ 1222 EXTENDED LIGHTS OUT(高斯消元)
- SVN 在 linux 下的配置
- yarn工作流程
- Github 开源:使用 .NET WinForm 开发所见即所得的 IDE 开发环境(Sheng.Winform.IDE)【2.源代码简要说明】
- git status 显示中文乱码
- 微信小程序登录流程及解析用户openid session_key,获取用户信息
- 爬虫之Selenium 动态渲染页面爬取
- Python入门-函数
- UpdatePanel1里面使用FileUpload控件
- Mysql 数据库操作之DDL、DML、DQL语句操作
- ecsop文件结构
- 使用OASGraph 暴露rest 接口为graphql api
- Excel数据导入PG库,字符串正则表达式