洛谷 P1973 [NOI2011] NOI 嘉年华

题目链接：P1973 [NOI2011] NOI 嘉年华

题解：

离散化每个活动时间后，用num[i][j]表示时间段[i,j]内的完整活动数量，用f[i][j]表示1-i时间内，第一个场所办了j个活动时，第二个场所能办的活动的最大数量,g[i][j]表示i-cnt时间内，第一个场所办了j个活动时，第二个场所能办的活动的最大数量,这样没有约束时就很好求了，有约束时我们枚举包含当前活动的区间左右端点，强制这段时间内活动都在第一个场地办，再枚举[1，左端点]和[右端点，时间结束]内在第一个场地办的活动数量，通过f和g函数就可以轻松求出第二个场地办的数量，此时复杂度是是O(N^5)，我们需要剪枝下，观察转移方程ans[k]=max(ans[k],min(num[i][j]+l+r,f[i][l]+g[j][r]))，因为f[i][l]和g[j][r]在i和j固定时都随着l或r递减，要使得min(num[i][j]+l+r,f[i][l]+g[j][r])最大，需要num[i][j]+l+r=f[i][l]+g[j][r],因为num[i][j]>=0，所以最优情况的l和r是满足g[j][r]>=r,f[i][l]>=l，再加上比较明显的剪枝，实际剪枝后只有O（n^3）左右

细节和注释见代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
	#ifndef local
	#define endl 'n'
#endif */
#define mkp make_pair
using namespace std;
using std::bitset;
typedef long long ll;
typedef long double ld;
const int inf=0x3f3f3f3f;
const ll MAXN=2e6+10;
const ll INF=1e18;
const ll N=2e5+100;
const ll mod=1e9+7;
const ll hash_p1=1610612741;
const ll hash_p2=805306457;
const ll hash_p3=402653189;
//-----------------------------------------------------------------------------------------------------------------*/
// ll head[MAXN],net[MAXN],to[MAXN],edge[MAXN],cost[MAXN]//费用;

//emplace_back()  等于push_back(),但效率更高,传输pair时emplace_back(i,j)==push_back({i,j}) 
// vector>edge; 二维虚拟储存坐标 
//-----------------------------------------------------------------------------------------------------------------*/
  mapmp; 
  //emplace_back() 
int s[210],t[210];
int num[410][410];//记录区间[i,j]内被完整包裹的活动数量
int f[410][210];//1-i时间内，第一个场所办了j个活动时，第二个场所能办的活动的最大数量
int g[410][210];//i-cnt时间内，第一个场所办了j个活动时，第二个场所能办的活动的最大数量
int ans[210];//各个答案
int main(){
/*cout<n;
	vectorb;
	for(int i=1;i<=n;i++){
		cin>>s[i]>>t[i];
		t[i]+=s[i];
		b.emplace_back(s[i]);
		b.emplace_back(t[i]);
	}
	//---------------------离散化----------
	sort(b.begin(),b.end());
	int cnt=0;
	mp[b[0]]=++cnt;
	for(int i=1;i=1;l--){
			for(int r=t[i];r<=cnt;r++){
				num[l][r]++;
			}
		}
	}
	//----------------求f和g数组
	memset(f,-inf,sizeof(f));
	memset(g,-inf,sizeof(g));
	for(int i=1;i<=cnt;i++){
		f[i][0]=0;
		g[i][0]=0;
	}
	for(int i=1;i<=cnt;i++){
		for(int j=0;j<=n;j++){
			for(int k=1;k<=i;k++){
				f[i][j]=max(f[i][j],f[k][j]+num[k][i]);//[k,i]段内活动在第二个场所办
				if(j>=num[k][i]){
					f[i][j]=max(f[i][j],f[k][j-num[k][i]]);//[k,i]段内活动在第一个场所办
				}
			}
			ans[0]=max(ans[0],min(f[i][j],j));
		}
	}
	for(int i=cnt;i>=1;i--){
		for(int j=0;j<=n;j++){
			for(int k=cnt;k>=i;k--){
				g[i][j]=max(g[i][j],g[k][j]+num[i][k]);//[k,i]段内活动在第二个场所办
				if(j>=num[i][k]){
					g[i][j]=max(g[i][j],g[k][j-num[i][k]]);//[k,i]段内活动在第一个场所办
				}
			}
		}
	}
	for(int k=1;k<=n;k++){//必须选择第k个活动
		for(int i=s[k];i>=1;i--){//包含活动k的区间[i,j]
			for(int j=t[k];j<=cnt;j++){
				for(int l=0;l<=num[1][i];l++){//[1,i]中在第一个活动场地举办的活动数
					for(int r=0;r<=num[j][cnt];r++){//[1,i]中在第一个活动场地举办的活动数
						ans[k]=max(ans[k],min(num[i][j]+l+r,f[i][l]+g[j][r]));
						if(g[j][r]

洛谷 P1973 [NOI2011] NOI 嘉年华

C/C++/C#相关栏目本月热门文章