样例过不去。。。求助
查看原帖
样例过不去。。。求助
216438
Dreamsuzki楼主2020/6/13 11:39

思路跟第 44 篇题解感觉差不多。但样例过不去QwQQwQ。求助

#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}这一行

2020/6/13 11:39
加载中...