#include <bits/stdc++.h> using namespace std; int huhe[105], huhet[105], huopao1[15], huopao2[15], power[15], prize[15], qinkuang[15], minn = 10000000; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { int a, b, c; cin >> a >> b >> c; for (int j = a; j <= b; j++) { huhe[j] = c; } } for (int i = 1; i <= m; i++) { cin >> huopao1[i] >> huopao2[i] >> power[i] >> prize[i]; } int cishu = 1; for (int i = 1; i <= m; i++) { cishu *= 2; } for (int i = 1; i <= cishu; i++) { int ans = 0; qinkuang[m] += 1; for (int j = m; j >= 1; j--) { if (qinkuang[j] >= 2) { qinkuang[j] -= 2; qinkuang[j - 1]++; } } for (int j = 1; j <= 105; j++) { huhet[j] = huhe[j]; } for (int j = 1; j <= m; j++) { if (qinkuang[j]) { ans += prize[j]; for (int k = huopao1[j]; k <= huopao2[j]; k++) { huhet[k] -= power[j]; } } } bool flag = true; for (int j = 1; j <= 100; j++) { if (huhet[j] > 0) { flag = false; break; } } if (flag && ans < minn) { minn = ans; } } cout << minn; return 0; }

啊啊啊啊啊啊啊啊啊啊

一眼看出二进制枚举

#include<bits/stdc++.h>
using namespace std;

const int N=140;
const int INF=0x3f3f3f3f;
int n,m,cf[N],c[N],datac[N],minn=INF;
struct Huhe{
	int s,t,p;
}h[N];
struct Bomb{
	int s,t,p,m;
}a[N];

int main()
{
	
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		cin>>h[i].s>>h[i].t>>h[i].p;
		cf[h[i].s]+=h[i].p;
		cf[h[i].t+1]-=h[i].p;
	}
	for(int i=1;i<=10;++i)//*
	{
		c[i]=c[i-1]+cf[i];
		datac[i]=c[i];
	}
	for(int i=1;i<=m;++i)
	{
		cin>>a[i].s>>a[i].t>>a[i].p>>a[i].m;
	}	
	
		
	for(int i=1;i<(1<<m);++i)
	{
		memset(cf,0,sizeof(cf));
		for(int i=0;i<=100;++i)c[i]=datac[i];
		for(int i=1;i<=100;++i)cf[i]=c[i]-c[i-1];
		
		int ans=0;
		for(int j=0;j<m;++j)
		{
			if(i>>j&1)
			{
				cf[a[j+1].s]-=a[j+1].p;
				cf[a[j+1].t+1]+=a[j+1].p;
				ans+=a[j+1].m;
			}
		}
		bool flag=1;
		for(int i=1;i<=10;++i)//*
		{
			c[i]=c[i-1]+cf[i];
			if(c[i]>0)
			{
				flag=0;
				break;
			}
		}
		if(flag==1)
		{
			minn=min(minn,ans);
		}
	}
	cout<<minn;
	return 0;
}

调了半个小时终于过样例了，兴冲冲地就交上去了。。。

结果！

上述代码两处标 $*$ 的地方没改成 $100$ ! 写挂了！变九分力！！

赛后才发现hhh。。。

呜呜呜我的100分啊啊啊啊

AC CODE

#include<bits/stdc++.h>
using namespace std;

const int N=140;
const int INF=0x3f3f3f3f;
int n,m,cf[N],c[N],datac[N],minn=INF;
struct Huhe{
	int s,t,p;
}h[N];
struct Bomb{
	int s,t,p,m;
}a[N];

int main()
{
	
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		cin>>h[i].s>>h[i].t>>h[i].p;
		cf[h[i].s]+=h[i].p;
		cf[h[i].t+1]-=h[i].p;
	}
	for(int i=1;i<=100;++i)
	{
		c[i]=c[i-1]+cf[i];
		datac[i]=c[i];
	}
	for(int i=1;i<=m;++i)
	{
		cin>>a[i].s>>a[i].t>>a[i].p>>a[i].m;
	}	
	
		
	for(int i=1;i<(1<<m);++i)
	{
		memset(cf,0,sizeof(cf));
		for(int i=0;i<=100;++i)c[i]=datac[i];
		for(int i=1;i<=100;++i)cf[i]=c[i]-c[i-1];
		
		int ans=0;
		for(int j=0;j<m;++j)
		{
			if(i>>j&1)
			{
				cf[a[j+1].s]-=a[j+1].p;
				cf[a[j+1].t+1]+=a[j+1].p;
				ans+=a[j+1].m;
			}
		}
		bool flag=1;
		for(int i=1;i<=100;++i)
		{
			c[i]=c[i-1]+cf[i];
			if(c[i]>0)
			{
				flag=0;
				break;
			}
		}
		if(flag==1)
		{
			minn=min(minn,ans);
		}
	}
	cout<<minn;
	return 0;
}

谨以此题解祭奠我失去的 $100$ 分

和本应变成19的排名QAQ

这个故事告诉我们，一开始先把全部分范围的数据开好。。。（除非骗分

状态压缩枚举

#include <bits/stdc++.h>
using namespace std;

const int maxn=2e1+5,maxm=1e1+5;
int N,M;
int s[maxn],t[maxn],c[maxn];
int a[maxm],b[maxm],p[maxm],m[maxm];
int f[1000],cd[1000];//fi为第i个巢穴收到的攻击 
bool check(){
	for(int i=1;i<=100;i++) if(f[i]<cd[i]) return false;
	return true;
}
int main(){
	cin >> N >> M;
	for(int i=0;i<N;i++){
		cin >> s[i] >> t[i] >> c[i];
		for(int k=s[i];k<=t[i];k++) cd[k]=c[i];
	} 
	int ans=0x3f3f3f3f;
	for(int i=0;i<M;i++) cin >> a[i] >> b[i] >> p[i] >> m[i];
	for(int pt=0;pt<(1<<(M));pt++){
		memset(f,0,sizeof(f));//清空 
		int sum=0;
		for(int i=0;i<M;i++){
			if(pt&(1<<i)){//有选i 
				sum+=m[i];
				for(int k=a[i];k<=b[i];k++) f[k]+=p[i];
			}
			if(check()) ans=min(ans,sum);
		}
	}
	cout << ans << endl;
	return 0;
}

二进制枚举即可

#include <bits/stdc++.h>
using namespace std;
int n, m;
int mp[200005], st[200005];
int minn = INT_MAX, maxn;
int a[15], b[15], c[25], p[15], q[15];
int main()
{
	cin >> n >> m;
	for(register int i = 1; i <= n; i++){
		int s, t;
		cin >> s >> t >> c[i];
		maxn = max(maxn, t);
		for(register int j = s; j <= t; j++) mp[j] = st[j] = c[i];//标记 
	} 
	for(register int i = 1; i <= m; i++) cin >> a[i] >> b[i] >> p[i] >> q[i];
	for(register int i = 0; i <= (1 << m); i++){
		int cost = 0;
		int j = i, t = 0;
		while(j){//二进制枚举 
			t++;
			if(j & 1){//买了第t个火炮
				cost += q[t]; 
				for(register int l = a[t]; l <= b[t]; l++) mp[l] -= p[t];
			}
			j >>= 1;
		}
		bool flag = 1;
		for(register int k = 1; k <= maxn; k++){
			if(mp[k] > 0) flag = 0;
		} 
		if(flag) minn = min(minn, cost);
		for(register int k = 1; k <= maxn; k++) mp[k] = st[k];
	}
	cout << minn;
	return 0;
}