三天写了一道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]表示可以高度不变不能下降。。
转移看代码吧。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | #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);} |
2015年11月03日 19:27
快去看lbn的0.7K飞扬的南小鸟
2015年11月04日 20:17
@Flandre Scarlet: %缩代码大师xmc&lbn