Noip 2014 날아다니는 새

컨디션

옮기다

for(int i=1;i<=m;i++) dp[0][i]=0;

for(int j=jum[i].x;j<=jum[i].x+m;j++)
    dp[i][j]=min(dp[i-1][j-jum[i].x],dp[i][j-jum[i].x])+1;

for(int j=m+1;j<=jum[i].x+m;j++)
    dp[i][m]=min(dp[i][m],dp[i][j]);

for(int j=1;j<=m-jum[i].y;j++)
    dp[i][j]=min(dp[i][j],dp[i-1][j+jum[i].y]);

for(int j=1;jhigh[i];j--) dp[i][j]=inf;

\(\tt{code}\)

#include
#include
#include
#include
#define inf 0x7ffffff
#define gc getchar();
using namespace std;
int read(){int k=0;char c=gc;while(!isdigit(c))c=gc;while(isdigit(c)){k=k*10+c-48;c=gc;}return k;}
int read_c(){int k=0;char c=gc;while(c'z')c=gc;return c-'a';}
struct hhh{
    int x,y;
}jum[10010];
int high[10010],low[100010],flag[100010];
int dp[10010][2010];
int main(){
    int n=read(),m=read(),k=read();
    //=======    
    for(int i=1;i<=n;i++)
      jum[i].x=read(),jum[i].y=read();
    for(int i=1;i<=n;i++) low[i]=1, high[i]=m;
    for(int i=1;i<=k;i++){
        int p=read(),l=read(),h=read();
        flag[p]=1; low[p]=l+1; high[p]=h-1;;    
    }
    memset(dp,127,sizeof(dp));
    //======DP  
    for(int i=1;i<=m;i++) dp[0][i]=0;
    for(int i=1;i<=n;i++){
        for(int j=jum[i].x;j<=jum[i].x+m;j++)
          dp[i][j]=min(dp[i-1][j-jum[i].x],dp[i][j-jum[i].x])+1;
          
        for(int j=m+1;j<=jum[i].x+m;j++)
          dp[i][m]=min(dp[i][m],dp[i][j]);
          
        for(int j=1;j<=m-jum[i].y;j++)
          dp[i][j]=min(dp[i][j],dp[i-1][j+jum[i].y]);
          
        for(int j=1;jhigh[i];j--)
          dp[i][j]=inf;
    }
    //    
    int ans=inf;
    for(int i=low[n];i<=high[n];i++)
      if(dp[n][i]<=100000)
        ans=min(ans,dp[n][i]);
    if(ans!=inf)
      printf("1
%d",ans);
    else{
        ans=0;
        for(int i=1;i<=n;i++){
            bool hhh=0;
            for(int j=1;j<=m;j++)
              if(dp[i][j]<=100000){
                  if(flag[i]) ans++;
                  hhh=1; break;
              }
            if(!hhh) break;
        }
        printf("0
%d",ans);
    }
    return 0;
}