【LGR-161-Div.3】洛谷基础赛 #4 P9688 Colo.

原题链接: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))

#include
#include
#include
#include
#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;

vectore[maxn];



signed main()
{
    cin >> n >> k;

    for (int i = 1; i > a[i];
        if (!l[a[i]])l[a[i]] = i;           //如果这种颜色的最左边位置还为0，那么此时就是它的最左边位置
        r[a[i]] = i;                        //不断更新这种颜色的最右边
    }
    for (int i = 1; i > w[i];
    }


    for (int i = 0; i a[j])e[a[i]].push_back(a[j]);//,cout

​

机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net