原题链接:P9688 Colo.
很显然,能够共存的颜色一定不会相交,所以可以记录每个颜色最左边的位置和最右边的位置,我们对于每个颜色只考虑,这个颜色左边的可以和这个颜色共存的额颜色
用f[i][j]表示当前考虑i这种颜色,选i这种颜色,然后在i这种颜色之前(包括这种颜色)一共选了j种颜色的最大价值
那么很显然,我们可以枚举i这种颜色左边的可以和i共存的颜色,用k代表,依次取不选k和选了k再选i的最大值,最终再取最大值
也就是,对于每一个j,我们都做一遍dp(i,j)=max(dp(j,j−1)+w[i],dp(i,j))文章来源:https://www.toymoban.com/news/detail-741844.html
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int maxn = 10020;
int a[maxn]; //存储序列
int l[maxn], r[maxn]; //l[i]记录i这种颜色最左边的位置,r[i]记录i这种颜色最右边的位置
int w[maxn]; //w[i]存储i这种颜色的价值
int f[maxn][maxn]; //f[i][j]表示的是选择i这种颜色,并且一共学了j种颜色的最大价值
//那么我们考虑所有可以和i这种颜色一块保留的颜色并放到i前面的,例如jk,比较保留jk和不保留jk的结果
//也就是f[i][j]=max(f[i][j],f[i][j-1]+w[jk])
int n, k;
vector<int>e[maxn];
signed main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (!l[a[i]])l[a[i]] = i; //如果这种颜色的最左边位置还为0,那么此时就是它的最左边位置
r[a[i]] = i; //不断更新这种颜色的最右边
}
for (int i = 1; i <= n; i++)
{
cin >> w[i];
}
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= k; j++)f[i][j] = -1e18; //这里的初始化之所以i从0开始,j从1开始,是为了让f[i][0]=0,再加上后面e[a[i]].push_back(0);可以保证,第一次执行
/*
for (int p = 1; p <= k; p++) {
f[a[i]][p] = max(f[a[i]][p], f[v][p - 1] + w[a[i]]);
}
可以把f[a[i][1]设置成w[a[i]]
*/
}
for (int i = 1; i <= n; i++) {
e[a[i]].push_back(0);
for (int j = 1; j <= n; j++) {
if (i == j)continue;
if (r[a[j]]<l[a[i]] && a[i]>a[j])e[a[i]].push_back(a[j]);//,cout<<a[i]<<" "<<a[j]<<endl;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < e[a[i]].size(); j++) {
int v = e[a[i]][j];
for (int p = 1; p <= k; p++) {
f[a[i]][p] = max(f[a[i]][p], f[v][p - 1] + w[a[i]]);
}
}
}
int mx = -1;
for (int i = 1; i <= n; i++)mx = max(mx, f[i][k]);
cout << mx;
return 0;
}
文章来源地址https://www.toymoban.com/news/detail-741844.html
到了这里,关于【LGR-161-Div.3】洛谷基础赛 #4 P9688 Colo.的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!