HDU 2159（dp46）

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int a[105], b[105]; int dp[105][105]; int main() { int N, M, K, S, i, j, k; while(scanf("%d%d%d%d", &N, &M, &K, &S) != EOF) { for(i = 1; i <= K; i++) scanf("%d%d", &a[i], &b[i]); memset(dp, 0, sizeof(dp)); for(i = 1; i <= M; i++) { for(j = 1; j <= S; j++) { for(k = 1; k <= K; k++) if(i - b[k] >= 0) { dp[i][j]=max(dp[i][j],dp[i - b[k]][j - 1] + a[k]); } } if (dp[i][S] >= N) break; } printf("%d\n", M - i); } return 0; }