10.18二中校内T2 区间dp

买书

街道上一共有?家书店，这些书店排成了一排。
这一天，佳佳的老师要求全班的学生去买一本学习资料。班里一共有m名学生，每名学生回家时都会走过这条街道的某一段，第i名学生会经过第li家书店到第ri家书店这一段路。由于同学们对他们要走过的路非常熟悉，他们会选择路上最便宜的一家书店买书。
对于第i个同学，如果最便宜的价格大于ci，他就会因为穷而不买书。
现在佳佳想知道，这?家书店对这本书各自卖多少钱，才可以让学生花的总钱数最大。

solution

思路
首先可以对c进行离散化 设f[i][j][l]为从i到j这段区间最小值大于等于l所能获得的最大利益

怎样转移,枚举区间分界点k 设g[l]为左端点在i-k,右端点在k-j，最小值大于等于l的区间的个数
网络
转移方程：
f[i][j][l]=max(f[i][j][l+1],f[i][k-1][l]+f[k+1][j][l]+g[l]*c[l];

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
	int l,r,c;
}a[510];
bool cmp(node a,node b)
{
	return a.c<b.c;
}
int val[510],cc=0;
int g[510];
int f[60][60][510];
int main()
{
	//freopen("book.in","r",stdin);
	//freopen("book.out","w",stdout);
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].l>>a[i].r>>a[i].c;
	}
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		if(a[i].c!=a[i-1].c)
		{
			val[++cc]=a[i].c;
			a[i].c=cc;
		}
	}
	//离散化
	for(int len=1;len<=n;len++)//枚举区间长
	{
		for(int i=1;i+len-1<=n;i++)//左端点
		{
			int j=i+len-1;//右端点
			for(int k=i;k<=j;k++)// 从k割开
			{
				memset(g,0,sizeof(g));
				for(int p=1;p<=m;p++)
				{
					if(a[p].l>=i&&a[p].l<=k&&a[p].r>=k&&a[p].r<=j)//找a[p]横跨k
					{
						g[a[p].c]++;
					}
				}
				for(int p=cc;p>=1;p--)
				{
					g[p]+=g[p+1];//前缀和
					f[i][j][p]=max(f[i][j][p],f[i][k-1][p]+f[k+1][j][p]+g[p]*val[p]);//取
					f[i][j][p]=max(f[i][j][p],f[i][j][p+1]);//不取
				}
			}
		}
	}
	cout<<f[1][n][1]<<endl;
	return 0;
}