题目链接
题意分析
我们令\(dp[i][j][k]\)表示当前区间\([i,j]\)最小价格为\(k\)的最大收益
那么状态转移方程就是
\[dp[i][j][k]=max\{dp[i][pos-1][x]+dp[pos+1][j][y]+cnt[pos][k]* k\}
\]
\[x,y≥k
\]
\(cnt[pos][k]\) 表示\([i,j]\)包含的区间中穿过
由于涉及到了输出方案 所以我们还要记录一些值
首先我们的\(dp[i][j][k]\)表示当前区间\([i,j]\)最小价格为\(≥k\)的最大收益
\(pos[i][j][k]\)表示当前状态的决策点
又因为\(dp[i][j][k]=max\{dp[i][j][l]\}(l≥k)\)
那么\(pre[i][j][k]=l\)就是继承最大值的的那个\(l\)
然后我们递归处理即可
同时涉及到了空间的问题 我们需要对价格进行离散化
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 58
#define IL inline
#define M 4050
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
T __=0,___=1;char ____=getchar();
while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
_=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
struct Node{
int le,ri,d;
}e[M];
int n,m,tot;
int res[M],ans[M],cnt[N][M];
int dp[N][N][M],pre[N][N][M],pos[N][N][M];
IL void getans(int le,int ri,int at)
{
if(le>ri) return;
int now=pos[le][ri][at=pre[le][ri][at]];
ans[now]=res[at];
getans(le,now-1,at);getans(now+1,ri,at);
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);read(m);
for(R int i=1;i<=m;++i) read(e[i].le),read(e[i].ri),read(e[i].d),res[i]=e[i].d;
sort(res+1,res+m+1);tot=unique(res+1,res+m+1)-res-1;
for(R int i=1;i<=m;++i) e[i].d=lower_bound(res+1,res+tot+1,e[i].d)-res;
// for(R int i=1;i<=m;++i) printf("%d%c",e[i].d,(i==m ? '\n':' '));
for(R int i=n;i;--i)
{
for(R int j=i;j<=n;++j)
{
for(R int k=i;k<=j;++k)
for(R int lim=0;lim<=tot;++lim)
cnt[k][lim]=0;
for(R int k=1;k<=m;++k)
if(i<=e[k].le&&e[k].ri<=j)
for(R int l=e[k].le;l<=e[k].ri;++l)
cnt[l][e[k].d]++;
for(R int k=i;k<=j;++k)
for(R int l=tot-1;l;--l)
cnt[k][l]+=cnt[k][l+1];
for(R int k=tot;k;--k)
{
int maxn=0;
for(R int l=i;l<=j;++l)
{
int wson=dp[i][l-1][k]+dp[l+1][j][k]+cnt[l][k]*res[k];
if(maxn<=wson) maxn=wson,pos[i][j][k]=l;
}
if(maxn>=dp[i][j][k+1]) dp[i][j][k]=maxn,pre[i][j][k]=k;
else dp[i][j][k]=dp[i][j][k+1],pre[i][j][k]=pre[i][j][k+1];
}
}
}
getans(1,n,1);
printf("%d\n",dp[1][n][1]);
for(R int i=1;i<=n;++i) printf("%d%c",ans[i],(i==n ? '\n':' '));
// fclose(stdin);
// fclose(stdout);
return 0;
}