第八屆“英拿科技杯”上海高校金馬程序設計聯賽暨東華大學邀請賽

儀表盤所有提交榜單

I. 孤星

單點時限:?2.0 sec

內存限制:?512 MB

𝑛(1≤103)?個干員，每個干員工資為?𝑤𝑖(1≤𝑤𝑖≤105)，貢獻值為?𝑣𝑖(1≤𝑣𝑖≤102)。

給出?𝑚(1≤𝑚≤105)次詢問，每次詢問：當你能承受的總工資為?𝑊(0≤𝑊≤109)?時，能收獲最大的貢獻值是多少。

輸入格式

第一行，兩個整數?𝑛,𝑚。

接下來?𝑛?行，每行兩個整數?𝑤𝑖,𝑣𝑖，表示每個干員的工資和貢獻值。

接下來𝑚行，每行一個數?𝑊，表示單次詢問中的可以承受的總工資。

輸出格式

輸出共𝑚行，每行一個數表示你的答案。

樣例

input

4 3
1 2
2 1
1 1
2 3
5
1
0

output

6
2
0

?思路：這個題目真的讓我對dp的理解加深了，其實這個就是一個大容量背包的問題，由于容量大，然后價值小，所以就可以考慮把下標和值調換一下，變成求一個價值最大為j的時候的最小的背包的總量dp[j]的問題，這樣的話我們進行一次打表，之后的詢問就可以O（logn）直接查詢。這里要注意的就是我們這里求最小的問題的dp數組并不是一個遞增的數組，原因就是因為不是每一個值都能往前倒到0，只有dp【0】為0的時候我們才能進行最小更新，所以我們進行需要進行一個后綴最小值處理，這樣的話我們就可以在查詢的時候減少時間復雜度。

#include "bits/stdc++.h"
using namespace std;
const int N = 1e9 + 3;
long long  w[2000], v[2000], dp[100010];
#define Inf 1000000005
//map<long long, long long> dp;
int main(){int n, m;cin>>n>>m;for(int i = 1; i <= n; i ++){cin>>w[i]>>v[i];}fill(dp, dp + 100010, Inf);
//		memset(dp, 0, sizeof(dp));dp[0] = 0;for(int i = 1; i <= n; i ++){for(int j = 100010; j >= 0; j --){dp[j] = dp[j];if(j - v[i] >= 0){dp[j] = min(dp[j], dp[j - v[i]] + w[i]);}}}long  long W;
//	sort(dp, dp + 100010);for (int i = 100000; i >= 0; i--) dp[i] = min(dp[i], dp[i + 1]);for(int k = 0; k < m; k ++){cin>>W;	long long  *ans = upper_bound(dp, dp + 100009, W);if(ans - dp == 0) cout<<0<<endl;else cout<<ans - dp - 1<<endl; }return 0;
}

?