题目意思很简单，
一道类似于背包的问题，问恰好超过背包容量的最小取值。并且需要计算n次，每计算一次都要将所有的物品的价值w[i] /= t，最后输出背包n次的总使用容量。
如果无法实现输出”No Answer”。
就是背包的变形，或者用队友的话说，当做dp做就好了，管它是不是背包呢。
主要就是状态转移方程了，其它没什么难点。
……感觉自己好水。
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 #define LL long long 8 9 const LL L = 1e17; 10 const int W = 10010; 11 12 int t_t; 13 int n, m, k, t; 14 LL a[W], b[W], dp[W]; 15 LL ans; 16 bool flag; 17 18 LL Min(LL x, LL y) 19 { 20 return (x == -1 || x > y) ? y : x; 21 } 22 23 int main() 24 { 25 //freopen("test.in", "r", stdin); 26 scanf("%d", &t_t); 27 for(int tm = 1; tm <= t_t; tm++) 28 { 29 scanf("%d%d%d%d", &n, &m, &k, &t); 30 for(int i = 0; i < m; i++) cin >> a[i]; 31 for(int i = 0; i < m; i++) cin >> b[i]; 32 33 ans = 0; 34 for(int ii = 1; ii <= n; ii++) 35 { 36 memset(dp, -1, sizeof(dp)); 37 dp[0] = 0; 38 flag = 0; 39 for(int i = 0; i < m; i++) 40 { 41 if(b[i] == 0) continue; 42 for(int j = 0; j <= k; j++) 43 { 44 int mid = j-b[i]>0 ? j-b[i] : 0; 45 //; 46 dp[j] = Min(dp[j], dp[mid]+a[i]); 47 //cout << b[i] << "#############" << dp[j] << endl; 48 } 49 } 50 //cout << "............................" << dp[k] << endl; 51 if(dp[k] == -1) {flag = 1; break;} 52 ans += dp[k]; 53 for(int i = 0; i < m; i++) b[i] /= t; 54 } 55 if(flag) cout << "No Answer" << endl; 56 else cout << ans << endl; 57 58 } 59 }