洛谷P1941
#include <bits/stdc++.h> using namespace std; const int inf=1e9; const int MN=10001; const int MM=1001; const int MK=10001; struct tube {int p,l/*downward*/,h/*upward*/;}s[MK]; bool cmp(tube a,tube b){return a.p<b.p;} int n,m,k,cnt=1; int up[MN],down[MN]; int f[MN][MM]; int dp() { for (int i=1;i<=n;++i) { for (int j=1;j<=m;++j) f[i][j]=inf; for (int j=1;j<=m;++j) if (j-up[i]>0) f[i][j]=min(f[i][j],min(f[i-1][j-up[i]],f[i][j-up[i]])+1); for (int j=m-up[i]+1;j<=m;++j) //'=' must be concentrated,for f[i-1][m] must be calced.don't for f[i][m] is twice and cut the '='. f[i][m]=min(f[i][m],min(f[i][j],f[i-1][j])+1); //!!! for (int j=1;j<=(m-down[i]);++j) f[i][j]=min(f[i][j],f[i-1][j+down[i]]); if (i==s[cnt].p) { for (int j=1;j<=m;++j) if (j>=s[cnt].h || j<=s[cnt].l) f[i][j]=inf; bool flag=true; for (int j=1;j<=m;++j) if (f[i][j]!=inf) { flag=false; break; } if (flag) {cout<<"0\n"<<cnt-1; return 0;} cnt++; } } int ans=inf; for (int i=1;i<=m;++i) ans=min(ans,f[n][i]); cout<<"1\n"<<ans; return 0; } int init() { cin>>n>>m>>k; for (int i=1;i<=n;++i) cin>>up[i]>>down[i]; for (int i=1;i<=k;++i) cin>>s[i].p>>s[i].l>>s[i].h; sort(s+1,s+k+1,cmp); return 0; } int main() { init(); dp(); return 0; }转载于:https://www.cnblogs.com/iyanhang/p/8324233.html
