2 条题解
-
1许致远___ (XZYxuzhiyuan) LV 7 @ 2022-8-8 19:19:09
#include<cstdio> #include<algorithm> using namespace std; const int N=10001,INF=0x7ffff; int n,m,k,x[N],y[N],dow[N],up[N],f[N][2001]; int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=0;i<n;++i)scanf("%d%d",&x[i],&y[i]); for(int i=1;i<=n;++i)dow[i]=0,up[i]=m+1; for(int i=1,p,l,h;i<=k;++i){ scanf("%d%d%d",&p,&l,&h); dow[p]=l,up[p]=h; } for(int i=1;i<=n;++i) for(int j=0;j<=m;++j) f[i][j]=INF; f[0][0]=INF; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ if(j>=x[i-1]){ f[i][j]=min(f[i][j],f[i-1][j-x[i-1]]+1); f[i][j]=min(f[i][j],f[i][j-x[i-1]]+1); } if(j==m) for(int k=j-x[i-1];k<=m;++k){ f[i][j]=min(f[i][j],f[i-1][k]+1); f[i][j]=min(f[i][j],f[i][k]+1); } } for(int j=dow[i]+1;j<=up[i]-1;++j) if(j+y[i-1]<=m) f[i][j]=min(f[i][j],f[i-1][j+y[i-1]]); for(int j=1;j<=dow[i];++j)f[i][j]=INF; for(int j=up[i];j<=m;++j)f[i][j]=INF; } int cnt=k,ans=INF; for(int i=n;i>=1;--i){ for(int j=dow[i]+1;j<=up[i]-1;++j) if(f[i][j]<INF) ans=min(ans,f[i][j]); if(ans!=INF)break; if(up[i]<=m)cnt--; } if(cnt==k)printf("1\n%d\n",ans); else printf("0\n%d\n",cnt); return 0; } ```cpp
-
02022-8-8 19:04:24@
/***************************************** 备注: ******************************************/ #include<queue> #include<math.h> #include<stack> #include<stdio.h> #include<iostream> #include<vector> #include<iomanip> #include<map> #include<string.h> #include<algorithm> using namespace std; const int MAXN = 1e4 + 5; const int MR = 2e3 + 5; const int INF = 0x3f3f3f3f; const int MOD = 998244353; int n, m, k; int x[MAXN], y[MAXN]; int high[MAXN], low[MAXN]; bool flag[MAXN]; int dp[MAXN][MR]; signed main() { cin >> n >> m >> k; for(int i = 1;i <= n; i++) { cin >> x[i] >> y[i]; } for(int i = 1;i <= n; i++) { //平路 high[i] = m; low[i] = 1; } for(int i = 1, xx, yy, zz;i <= k; i++) { cin >> xx >> yy >> zz; high[xx] = zz - 1; low[xx] = yy + 1; flag[xx] = 1; } memset(dp, INF, sizeof dp); for(int i = 1;i <= m; i++) { dp[0][i] = 0; } for(int i = 1;i <= n; i++) { //上去 for(int j = x[i] + 1;j <= x[i] + m; j++) { dp[i][j] = min(dp[i - 1][j - x[i]] + 1, dp[i][j - x[i]] + 1); } //顶端 for(int j = m + 1;j <= x[i] + m; j++) { dp[i][m] = min(dp[i][m], dp[i][j]); } //飞过了 for(int j = 1;j <= m - y[i]; j++) { dp[i][j] = min(dp[i - 1][j + y[i]], dp[i][j]); } //下去 for(int j = 1;j < low[i]; j++) { dp[i][j] = INF; } for(int j = high[i] + 1;j <= m; j++) { dp[i][j] = INF; } } int ans = INF; for(int i = 1;i <= m; i++) { ans = min(ans, dp[n][i]); } if(ans < INF) { cout << 1 << endl << ans; return 0; } ans = 0; int i, j;//在哪一个横坐标掉下去 for(i = n; i >= 1; i--) { for(j = 1; j <= m; j++) { if(dp[i][j] < INF)break; } if(j <= m)break; } for(int k = 1;k <= i; k++) { if(flag[k])ans++; } cout << 0 << endl << ans; return 0; }
- 1
信息
- ID
- 744
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 67
- 已通过
- 15
- 上传者