q234rty's Blog

三天写了一道NOIP题。。

题目在这里：http://uoj.ac/problem/17

暴力dp的方程是显然的：对于每一个i,j,更新dp[i+1][j-y[i]],dp[i+1][min(j+x[i]*k,m)](1<=k<=m)

然后发现min的部分是可以递推的。。

然后用dp[i][j][0]表示可以下降不能高度不变，dp[i][j][1]表示可以高度不变不能下降。。

转移看代码吧。。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
void init(){
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
int dp[10001][1001][2];
int l[10001],h[10001],x[10001],y[10001];
int main(){
    init();
    int n=readint(),m=readint(),k=readint();
    for(int i=0;i<n;i++){
        x[i]=readint(),y[i]=readint();
    }
    fill(l,l+n+1,0);
    fill(h,h+n+1,m+1);
    for(int i=1;i<=k;i++){
        int p=readint();
        l[p]=readint();
        h[p]=readint();
    }
    memset(dp,0x3f,sizeof(dp));
    memset(dp[0],0,sizeof(dp[0]));
    for(int j=0;j<=m;j++)
        dp[0][j][1]=INF;
    int maxr=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<=m;j++){
            if (j<=l[i] || j>=h[i]){
                dp[i][j][0]=INF;
                //printf("dp[%d][%d][1] is %d\n",i,j,dp[i][j][1]);
                //printf("dp[%d][%d][0] is %d\n",i,j,dp[i][j][0]);
            }
            dp[i+1][min(j+x[i],m)][0]=min(dp[i+1][min(j+x[i],m)][0],dp[i][j][0]+1);
            if (j>y[i])
                dp[i+1][j-y[i]][0]=min(dp[i+1][j-y[i]][0],dp[i][j][0]);
            dp[i+1][j][0]=min(dp[i+1][j][0],dp[i][j][1]);
            dp[i][min(j+x[i],m)][1]=min(dp[i][min(j+x[i],m)][1],dp[i][j][1]+1);
            dp[i][min(j+x[i],m)][1]=min(dp[i][min(j+x[i],m)][1],dp[i][j][0]+1);
            if (dp[i][j][0]<INF){
                maxr=i;
            }
            //printf("dp[%d][%d][1] is %d\n",i,j,dp[i][j][1]);
            //printf("dp[%d][%d][0] is %d\n",i,j,dp[i][j][0]);
        }
    int ans=INF;
    for(int i=0;i<=m;i++)
        ans=min(ans,dp[n][i][0]);
    if (ans>=INF){
        printf("0\n");
        int cnt=0;
        for(int i=0;i<=maxr;i++)
            if (h[i]<m+1)
                cnt++;
        printf("%d\n",cnt);
    }
    else printf("1\n%d\n",ans);

}