思路跟第 4 篇题解感觉差不多。但样例过不去QwQ。求助
#include<bits/stdc++.h>
#define ll long long
#define landingyu work();
#define AK return
#define IOI 0;
#define inf 0x3f3f3f3f
#define eps 0.00001
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int F[1000];
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)write(x/10);
putchar(x%10+'0');
}
int max3(int a,int b,int c){return max(max(a,b),c);}
int min3(int a,int b,int c){return min(min(a,b),c);}
int max4(int a,int b,int c,int d){return max(max(a,b),max(c,d));}
int min4(int a,int b,int c,int d){return min(min(a,b),min(c,d));}
struct node{
int id;
int h;
int l;
}a[10010];
int n,m,k,up[10010],down[10010],dp[2][10010],temp=1;
bool cmp(node a,node b){
return a.id<b.id;
}
void work(){
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++) up[i]=read(),down[i]=read();
for(int i=1;i<=k;i++) a[i].id=read(),a[i].l=read(),a[i].h=read();
sort(a+1,a+k+1,cmp);
memset(dp,0x3f3f3f3f,sizeof(dp));
for(int i=1;i<=m;i++) dp[0][i]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) dp[i&1][j]=0x3f3f3f3f;
for(int j=up[i]+1;j<=up[i]+m;j++) dp[i&1][j]=min(dp[(i-1)&1][j-up[i]],dp[i&1][j-up[i]])+1;
for(int j=m+1;j<=up[i]+m;j++) dp[i&1][m]=min(dp[i&1][m],dp[i&1][j]);
for(int j=1;j<=m-down[i];j++) dp[i&1][j]=min(dp[i&1][j],dp[(i-1)&1][j+down[i]]);
if(i==a[temp].id){
int ans=0x3f3f3f3f;
for(int j=1;j<=a[i].l;j++) dp[i&1][j]=0x3f3f3f3f;
for(int j=a[i].h;j<=m;j++) dp[i&1][j]=0x3f3f3f3f;
for(int j=1;j<=m;j++) ans=min(dp[i&1][j],ans);
if(ans==0x3f3f3f3f) {
cout<<0<<endl<<temp-1;
return;
}
temp++;
}
}
int ans=0x3f3f3f3f;
for(int i=1;i<=m;i++) ans=min(ans,dp[n&1][i]);
cout<<1<<endl<<ans;
}
int main(){landingyu AK IOI}
/*
------------------------
Author:库里Curry
Remark:(hard)bag dp
Difficulties:normal
------------------------
*/
禁止讨论int main(){landingyu AK IOI}
这一行