時間限制:5000ms 單點時限:1000ms 內存限制:256MB
小Ho很喜歡在課間去小賣部買零食。然而不幸的是，這個學期他又有在一教的課，而一教的小賣部姐姐以冷若冰霜著稱。第一次去一教小賣部買零食的時候，小Ho由于不懂事買了好一大堆東西，被小賣部姐姐給了一個“冷若冰霜”的眼神，食欲都下降了很多。
從那以后，小Ho就學乖了，去小賣部買東西只敢同時買3包以內的零食，并且價格加起來必須是5的整數倍，方便小賣部姐姐算價格。
但是小Ho不擅長計算，所以他把小賣部里所有零食的價格以及他對這個零食的渴望度都告訴了你，希望你能夠幫他計算出在不惹惱小賣部姐姐的前提下，能夠買到零食的渴望度之和最高是多少？
每個輸入文件包含多組測試數據，在每個輸入文件的第一行為一個整數Q，表示測試數據的組數。
每組測試數據的第一行為一個正整數N，表示小賣部中零食的數量。
接下來的N行，每行為一個正實數A和一個正整數B，表示這種零食的價格和小Ho對其的渴望度。
一種零食僅有一包。
對于100%的數據，滿足1 <= Q <= 10，1<=N<=50，0
對于每組測試數據，輸出一個整數Ans，表示小Ho可以獲得最大的渴望度之和。
1 4 0.5 6 4.5 7 5.0 4 2.0 9
17
本來覺得要用動規，看了一下數據量，暴力枚舉即可解決，時間復雜度n^3：：
#include<iostream>#include<cstdio>using namespace std;const int maxn=55;int a[maxn];int b[maxn];int main(){ int i,j,k; int Q,n; double tempa; scanf("%d",&Q); while(Q--) { scanf("%d", &n); for(i=0; i<n; i++) { scanf("%lf%d",&tempa,&b[i]); a[i]=int(tempa*10); } int max_des=0; for (i=0; i<n; i++) { for (j=i+1; j<n; j++) { for (k=j+1; k<n; k++) { int sum_val=a[i]+a[j]+a[k]; int sum_des=b[i]+b[j]+b[k]; if (sum_val%50 == 0){ if (sum_des > max_des) max_des=sum_des; } } } } for (i=0; i<n; i++) { for (j=i+1; j<n; j++) { int sum_val=a[i]+a[j]; int sum_des=b[i]+b[j]; if (sum_val%50 == 0){ if (sum_des > max_des) max_des=sum_des; } } } for (i=0; i<n; i++) { int sum_val=a[i]; int sum_des=b[i]; if (sum_val%50 == 0){ if (sum_des > max_des) max_des=sum_des; } }新聞熱點
疑難解答
