分析:
这是一个DP,没什么好说的,细节很烦人。
DP[i][j]表示到第i个位置,高度为j点最少的次数。
转移:
当j=m时
k属于[m-h,m]都可以向DP[i][j]转移,即dp[i][j]=min(dp[i-1][k]+1);
当j!=m时
dp[i][j]=min{dp[i-1][j-h]+1,dp[i-1][j+p]};
剩下的就是细节问题,没有别的了,细节巨恶心...
#include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> using namespace std; #define N 1005 #define inf 1<<30 int n,m,K; int f[N*10][N],dp[N*10][N]; int up[N*10],down[N*10],p[N*10]; struct node { int low,above; }block[N*10]; int main() { scanf("%d%d%d",&n,&m,&K); for(int i=0;i<n;i++) { scanf("%d%d",&up[i],&down[i]); block[i].low=0; block[i].above=m+1; p[i]=0; } block[n].low=0,block[n].above=m+1; for(int i=0;i<K;i++) { int x; scanf("%d",&x); scanf("%d%d",&block[x].low,&block[x].above); p[x]=1; } p[n]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { dp[i][j]=inf; } } dp[0][0]=inf; for(int i=1;i<=n;i++) { for(int j=up[i-1]+1;j<=m;j++) { if(j==m) { for(int k=m-up[i-1]+1;k<=m;k++) { dp[i][j]=min(dp[i][j],dp[i-1][k]+1); dp[i][j]=min(dp[i][j],dp[i][k]+1); } } dp[i][j]=min(dp[i][j],dp[i-1][j-up[i-1]]+1); dp[i][j]=min(dp[i][j],dp[i][j-up[i-1]]+1); } for(int j=max(1,block[i].low+1);j<=min(m-down[i-1],block[i].above-1);j++) { dp[i][j]=min(dp[i][j],dp[i-1][j+down[i-1]]); } for(int j=block[i].low;j>=0;j--) { dp[i][j]=inf; } for(int j=block[i].above;j<=m;j++) { dp[i][j]=inf; } } int ans=inf; int num=K; for(int i=n;i>=1;i--) { for(int j=block[i].low+1;j<=block[i].above-1;j++) { ans=min(ans,dp[i][j]); } if(ans<inf) { break; } if(p[i]==1) { num--; } } if(num>=K) { printf("1 %d ",ans); } if(num<K) { printf("0 %d ",num); } return 0; }