2 条题解

  • 1
    #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
    • 0
      @ 2022-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
      上传者