题解 P1328 【生活大爆炸版石头剪刀布】

· · 题解

f(i,j)->f(i-1,j+Y[i-1])

  ->f(i-1,j-k\*X[i-1])+k,k>0且j-k\*X[i-1]>0

完全背包式优化：

f(i,j)->f(i-1,j-X[i-1])+1
      ->f(i,j-X[i-1])+1
      ->f(i-1,j+Y[i-1])
#include<iostream>  
using namespace std;  
#include<cstdio>  
#include<cstring>  
#include<cmath>  
#include<algorithm>  
typedef short hd;  
char * ptr=(char *)malloc(1000000);  
int f[10001][1001];  
inline void in(hd &x){  
    while(*ptr<'0'||*ptr>'9')++ptr;  
    x=0;  
    while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';  
}  
int main(){  
    hd P[10000],down[10001],up[10001],X[10000],Y[10000],N,M,K,tmp,i,j;  
    int MAXN=2000000000;  
    freopen("birda.in","r",stdin);  
    freopen("birda.out","w",stdout);  
    //读入   
    fread(ptr,1,1000000,stdin);  
    in(N),in(M),in(K);  
    for(i=0;i<N;++i)in(X[i]),in(Y[i]);  
    for(i=0;i<=N;++i)up[i]=M+1;  
    for(i=0;i<K;++i)in(P[i]),in(down[P[i]]),in(up[P[i]]);  
    //初始化   
    sort(P,P+K);  
    memset(*f+1001,127,sizeof(f)-sizeof(int)*1001);  
    f[0][0]=MAXN;  
    //DP  
    for(i=1;i<=N;++i){  
        for(j=1;tmp=min((hd)(j+X[i-1]),M),j<=M;++j)f[i][tmp]=min(f[i][tmp],f[i-1][j]+1);  
        for(j=1;tmp=min((hd)(j+X[i-1]),M),j<M;++j)f[i][tmp]=min(f[i][tmp],f[i][j]+1);  
        for(j=M;j>Y[i-1];--j)f[i][j-Y[i-1]]=min(f[i][j-Y[i-1]],f[i-1][j]);  
        for(j=0;j<=down[i];++j)f[i][j]=MAXN;  
        for(j=up[i];j<=M;++j)f[i][j]=MAXN;  
        //判断当前列是否可达  
        j=1;  
        while(j<=M&&f[i][j]>=MAXN)++j;  
        if(j>M)break;  
    }  
    if(i>N)printf("1\n%d",*min_element(f[N]+1,f[N+1]));  
    else printf("0\n%d",lower_bound(P,P+K,i)-P);  
}