https://loj.ac/problem/10151
题目描述
?? 由 \(n\) 个位置, 每个位置有一定的价值, 每次可以选择一个位置 \(k\), 把区间 \([l,r]\) 分为 \(l\sim k\) 和 \(k+1\sim r\) 两段, 区间长度为 \(1\) 时停止, 总价值为每次将区间合并时左右端点的价值之和 \(\times\)\(k\) 位置的价值, 求最大价值及字典序最小的方案.
思路
?? 我们考虑用 \(f[i][j]\) 表示 \(i\sim j\) 的答案, 那么显然每一段都可以由确定的位置 \(k\) 转移过来, 取其中的最小值即可. 方程 \(f[i][j]=max\{f[i][k]+f[k+1][r]+(v[l]+v[r])*v[k]\}\), 在用一个数组记录答案即可. 最后暴力重新分解一遍即可.
代码
- #include <bits/stdc++.h>
- using namespace std;
- struct aa
- {
- int l,r;
- aa(int l=0,int r=0):l(l),r(r) {}
- };
- int read()
- {
- int res=0,w=1;
- char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
- return res*w;
- }
- void write(int x)
- {
- if(x<0){putchar('-');x=-x;}
- if(x>9)write(x/10);
- putchar(x%10+'0');
- }
- void writeln(int x)
- {
- write(x);
- putchar('\n');
- }
- int a[330],f[330][330],ans[330][330];
- void print(int l,int r)
- {
- queue<aa> q;
- q.push(aa(l,r));
- while(!q.empty())
- {
- aa now=q.front();q.pop();
- int k=ans[now.l][now.r];
- write(k);putchar(' ');
- if(k!=now.l)q.push(aa(now.l,k));
- if(k+1!=now.r)q.push(aa(k+1,now.r));
- }
- }
- int main()
- {
- int n=read();
- for(int i=1;i<=n;i++)
- a[i]=read();
- for(int len=2;len<=n;len++)
- for(int l=1;l<=n-len+1;l++)
- {
- int r=l+len-1;
- for(int k=l;k<r;k++)
- {
- int x=f[l][k]+f[k+1][r]+(a[l]+a[r])*a[k];
- if(x>f[l][r])
- {
- // cout<<l<<''<<r<<' '<<k<<' '<<x<<endl;
- // cout<<f[l][k]<<' '<<f[k+1][r]<<endl;
- f[l][r]=x;
- ans[l][r]=k;
- }
- }
- }
- writeln(f[1][n]);
- print(1,n);
- }
分离与合体
来源: http://www.bubuko.com/infodetail-3283304.html