【BZOJ-4380】Myjnie 区间DP

2023-01-04 13:53:33

4380: [POI2015]Myjnie

Time Limit: 40 Sec Memory Limit: 256 MBSec Special Judge
Submit: 162 Solved: 82
[Submit][Status][Discuss]

Description

有n家洗车店从左往右排成一排，每家店都有一个正整数价格p[i]。
有m个人要来消费，第i个人会驶过第a[i]个开始一直到第b[i]个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于c[i]，那么这个人就不洗车了。
请给每家店指定一个价格，使得所有人花的钱的总和最大。

Input

第一行包含两个正整数n,m(1<=n<=50，1<=m<=4000)。
接下来m行，每行包含三个正整数a[i],b[i],c[i](1<=a[i]<=b[i]<=n，1<=c[i]<=500000)

Output

第一行输出一个正整数，即消费总额的最大值。
第二行输出n个正整数，依次表示每家洗车店的价格p[i]，要求1<=p[i]<=500000。
若有多组最优解，输出任意一组。

Sample Input

7 5
1 4 7
3 7 13
5 6 20
6 7 1
1 2 5

Sample Output

43
5 5 13 13 20 20 13

HINT

Source

鸣谢Claris

Solution

这个区间dp好厉害啊，自己的转移并没有想到，最后是看着Claris的课件做的。

现将$c_{i}$离散化，然后区间dp

$dp[l][r][p]$表示区间$[l,r]$，最小价值为$p$的最大总和，$cnt[k][c]$表示经过$k$位置的费用$\geqslant c$的数量

转移时通过枚举最小值所在的位置$k$，来进行转移$dp[l][r][p]<--dp[l][k-1][p]+dp[k+1][r][p]+cost(k)$

还要记录方案，最后用dfs输出。

总的时间复杂度$O(N^{3}M)$

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

int N,M,a[],b[],c[],C[],price[],ls[],tp,top;

int from[][][],last[][][],cnt[][],dp[][][];

inline void Get(int l,int r,int p)

{

    if (l>r) return;

    int fr=from[l][r][p],la=last[l][r][p];

//    printf("%d  %d  %d  %d\n",l,r,p,fr);

    price[fr]=C[la];

    Get(l,fr-,la); Get(fr+,r,la);

}

int main()

{

    N=read(),M=read();

    for (int i=; i<=M; i++) a[i]=read(),b[i]=read(),C[i]=c[i]=read(),ls[++tp]=c[i];

    sort(ls+,ls+tp+);

    for (int i=; i<=tp; i++) if (ls[top]!=ls[i]) ls[++top]=ls[i];

    for (int i=,x; i<=M; i++) x=lower_bound(ls+,ls+top+,c[i])-ls,C[x]=c[i],c[i]=x;

//    for (int i=1; i<=M; i++) printf("%d  ",C[i]); puts("");

    for (int l=; l<=N; l++)

        for (int r=l; r<=N; r++)

            for (int p=; p<=M; p++)

                dp[l][r][p]=-0x3fffffff;

    for (int len=; len<=N; len++)

        for (int l=,r=l+len-; r<=N; l++,r++)

            {

                for (int k=l; k<=r; k++)

                    for (int i=; i<=M; i++)

                        cnt[k][i]=;

                for (int i=; i<=M; i++)

                    if (a[i]>=l && b[i]<=r)

                        for (int k=a[i]; k<=b[i]; k++)

                            cnt[k][c[i]]++;

                for (int k=l; k<=r; k++)

                    for (int i=M-; i; i--)

                        cnt[k][i]+=cnt[k][i+];

                for (int k=l; k<=r; k++)

                    for (int i=; i<=M; i++)

                        if (dp[l][k-][i]+dp[k+][r][i]+C[i]*cnt[k][i]>dp[l][r][i])

                            dp[l][r][i]=dp[l][k-][i]+dp[k+][r][i]+C[i]*cnt[k][i],

                            from[l][r][i]=k,last[l][r][i]=i;// from[l][r][i]=i;

                for (int i=M-; i; i--)

                    if (dp[l][r][i]<dp[l][r][i+])

                        dp[l][r][i]=dp[l][r][i+],

                        from[l][r][i]=from[l][r][i+],last[l][r][i]=last[l][r][i+];

//                printf("<%d , %d> == %d\n",l,r,dp[l][r][1]);

            }

    printf("%d\n",dp[][N][]);

    Get(,N,);

    for (int i=; i<=N; i++) printf("%d ",price[i]);

    return ;

}

码农公寓