题目大意

确定一个长度为的序列,使得个区间中小于等于的最小值(不存在,则为)之和最大。

题解

区间DP,状态表示表示序列区间中的价格最小值为的最大盈利。
离散化所有的,另
最后搜索一下方案即可。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define LL long long 
using namespace std;

const int Maxn=50;
const int Maxm=4000;

int n,m;
struct Cust{int l,r,c;}cs[Maxm+5];
int pool[Maxm+5],tot;
int cnt[Maxn+5][Maxn+5][Maxm+5];
LL dp[Maxn+5][Maxn+5][Maxm+5];
LL mx[Maxn+5][Maxn+5][Maxm+5];
int ans[Maxn+5];

inline LL getValue(int l,int r,int mid,int c){
    return mx[l][mid-1][c]
        + mx[mid+1][r][c]
        + 1LL * (cnt[l][r][c] - cnt[l][mid-1][c] - cnt[mid+1][r][c]) * pool[c];
}

void dfs(int l,int r,int c){
    if (l>r) return;

    int now=0;
    for (int i=c;i<=tot;i++) 
        if (mx[l][r][c]==dp[l][r][i]){
            now=i;
            break;
        }

    for (int mid=l;mid<=r;mid++){
        if (dp[l][r][now]==getValue(l,r,mid,now)){
            dfs(l,mid-1,now);
            dfs(mid+1,r,now);
            ans[mid]=now;
            return;
        }
    }
}

int main(){
    // freopen("in.txt","r",stdin);

    scanf("%d%d",&n,&m);
    tot=0; 
    for (int i=1;i<=m;i++) 
        scanf("%d%d%d",&cs[i].l,&cs[i].r,&cs[i].c);

    for (int i=1;i<=m;i++) pool[++tot]=cs[i].c;
    sort(pool+1,pool+tot+1); 
    tot=unique(pool+1,pool+tot+1)-pool-1;

    //memset(cnt,0,sizeof(cnt));
    //memset(dp,0,sizeof(dp));
    //memset(mx,0,sizeof(mx));

    for (int i=1;i<=m;i++) {
        cs[i].c=lower_bound(pool+1,pool+tot+1,cs[i].c)-pool;
        for (int l=1;l<=n;l++) 
            for (int r=l;r<=n;r++) 
                if (l<=cs[i].l && cs[i].r<=r) cnt[l][r][cs[i].c]++;
    }

    for (int l=1;l<=n;l++) for (int r=l;r<=n;r++) {
        for (int c=tot;c>=1;c--){
            cnt[l][r][c]+=cnt[l][r][c+1];
        }
    }

    for (int len=1;len<=n;len++){
        for (int l=1;l<=n;l++){
            int r=l+len-1; if (r>n) break;
            for (int c=1;c<=tot;c++){
                for (int mid=l;mid<=r;mid++){
                    dp[l][r][c]=max(dp[l][r][c],getValue(l,r,mid,c));
                }
                //printf("DP[%d][%d][%d]=%lld\n",l,r,c,dp[l][r][c]);
            }
            for (int c=tot;c>=1;c--) mx[l][r][c]=max(mx[l][r][c+1],dp[l][r][c]);
        }
    }

    printf("%lld\n",mx[1][n][1]);
    memset(ans,-1,sizeof(ans)); dfs(1,n,1);
    for (int i=1;i<=n;i++){
        printf("%d ",pool[ans[i]]);
    }
    printf("\n");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注