NC21668. 牛牛去买球
描述
输入描述
第一行输入两个整数n,K (1≤ n≤50, 1 ≤ K ≤ 10000)
第二行输入n个整数表示a数组
第三行输入n个整数表示b数组
第三行输入n个整数表示c 数组
1 ≤ ai,bi,ci ≤ 10000
输出描述
输出一个整数，如果无法达成目的，输出$-1$
示例1
输入:
2 10 6 5 4 4 1 1
输出:
2
示例2
输入:
2 10 5 5 4 4 1 1
输出:
-1
示例3
输入:
1 9 10 5 13
输出:
13
示例4
输入:
5 10 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
输出:
10
示例5
输入:
5 17 1 2 3 4 15 1 2 3 4 5 1 2 3 4 5
输出:
9
C++11(clang++ 3.9) 解法, 执行用时: 15ms, 内存消耗: 620K, 提交时间: 2019-07-29 23:55:06
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 0x3f3f3f3f;
int dp[20010];
int ball[5][55],n,k;
int main(){
int ans = inf;
cin >> n >> k;
for(int i = 0;i < 4;i++)
for(int j = 0;j < n;j++){
if(i == 2) ball[i][j] = ball[0][j]+ball[1][j]+2;
else{
cin >> ball[i][j];
if(i != 3) ball[i][j]--;
}
}
for(int u = 0;u < 3;u++){
memset(dp,0x3f,sizeof(dp));
dp[0] = 0;
for(int i = 0;i < n;i++){
for(int j = 20005;j >= 0;j--){
int x = ball[u][i];
if(j-x >= 0 && dp[j-x] != inf && dp[j] > dp[j-x]+ball[3][i])
dp[j] = dp[j-x]+ball[3][i];
}
}
int m = (u == 2?(k<<1)-1:k);
for(int i = m;i <= 20005;i++)
ans = min(ans,dp[i]);
}
if(ans == inf) printf("-1\n");
else printf("%d\n", ans);
return 0;
}