信息
- ID
- 3147
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 190
- 已通过
- 40
- 上传者
一眼看出二进制枚举
#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分啊啊啊啊
#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;
}