BabbleDay's Blog
Happy Coding
uva 10130 Super Sale
BabbleDay
posted @ 2013年4月17日 13:43
in 刷题防身
, 815 阅读
难得的一次过啊。。。经典的01背包问题，那句注释是重点
#include <iostream>
#include <cstring>
#define max(a, b) ( a > b ? a: b)
using namespace std;
//store the max price with weight no more than a[i]
int a[31];
void the_case()
{
memset(a, 0, sizeof(a));
int num, p, w, maxw;
cin >> num;
while(num--)
{
cin >> p >> w;
for (int i=30; i>=w; i--)//注意是倒序，从没更新的数据实现更新
{
a[i] = max(a[i-w]+p, a[i]);
}
}
cin >> num;
int ans=0;
while(num--)
{
cin >> maxw;
ans += a[maxw];
}
cout << ans << endl;
}
int main()
{
int c;
cin >> c;
while(c--)
{
the_case();
}
}
2023年9月28日 22:44
Nagaland Board 8th Class Book 2024 for Science, Social Science, English, Hindi, Mathematics, EVS, Various Provide in School Wise Free Distribution in Government School, NBSE High School Various Class Complete Students Do not Waste Summers Holidays, Download Nagaland Board Class Book 2024 Regular Practice new Lessions for Students Best idea Students Method.Nagaland Board Class Textbook 2024 Download NBSE 8th Class Textbook 2024 Available Official Website, Our Portal Provide Nagaland Board High School Books 2024 Download, Hindi Medium, English Medium and Urdu Medium Textbooks.
2024年1月28日 05:51
Board Model Papers 2024 Download with Suggestions for 10th Class Textbooks 2024 Pdf Download and SSLC New Syllabus Sample Question Paper 2024 and different types of model papers boardmodelpaper.com and question papers for following the website and Arts, Science, Commerce Stream Subject Wise Solved Question Bank for Hindi & English Medium Students with Exam Pattern & Blueprint and subject Wise with 11th & 12th Question Bank 2024 for General & Vocational Course Languages & Subjects Important Question for the above link.