POJ 1742 dp
10501 단어 dp
전송문 POJ 1742
다중 섹션 및 문제
dp[i+1][j]: = 전 i종수로 j를 더하고 받았을 때 i종수는 최대 몇 개(j를 더할 수 없는 경우 - 1)dp[i+1] [j]: = 전 i종수로 더하고 받았을 때 i종수는 최대 몇 개(j를 더할 수 없는 경우 - 1)dp[i+1] [j]: = 전 i종수로 더하고 받았을 때 i종수는 최대 몇 개(j를 더할 수 없는 경우 - 1)dp[i+1] [j]:(j를 가화할 수 없는 경우 -4.1)
수조를 중복 활용하여 최종적으로 dp[i]≥0, i>0dp[i]\geq0, i>0dp[i]≥0, i>0의 ii 수량을 만족시키면 답이다.
#include
#include
#include
#include
#include
#include
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define abs(x) ((x) < 0 ? -(x) : (x))
#define INF 0x3f3f3f3f
#define delta 0.85
#define eps 1e-3
#define PI 3.14159265358979323846
#define MAX_N 105
#define MAX_M 100005
using namespace std;
typedef pair<int, int> P;
int N, M;
int A[MAX_N], C[MAX_N];
int dp[MAX_M];
int main(){
while(~scanf("%d%d", &N, &M) && (N | M)){
memset(dp, -1, sizeof(dp));
for(int i = 0; i < N; i++) scanf("%d", A + i);
for(int i = 0; i < N; i++) scanf("%d", C + i);
dp[0] = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j <= M; j++){
if(dp[j] >= 0) dp[j] = C[i];
else if(j < A[i] || dp[j - A[i]] <= 0) dp[j] = -1;
else dp[j] = dp[j - A[i]] - 1;
}
}
int res = 0;
for(int i = 1; i <= M; i++) if(dp[i] >= 0) ++res;
printf("%d
", res);
}
return 0;
}