题目链接

题意分析

首先我们肯定会贪心的走从根节点到叶子结点最长的一条链

首先没有过剩的就好办了

但是有的话我们就一边往下走一边走分支

分支上每一个点平均走过两次

所以我们把剩下的除以\(2\)即可

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 500008

#define IL inline

#define M 1008611

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

}

巴特西

P3698 [CQOI2017]小Q的棋盘

题目链接

题意分析

CODE:

HEOI 2019 RP++

最新文章

热门文章