漲了111 rating 真是耗rp啊.....300pt
有一個1到N(N<50)的排列，序列中的一些數被隱藏了(表示為0)。你每一次都可以選擇數列中某個位置的一個數作為自己的得分，不論這個數是否被隱藏，你都會得到相應的分數。
請問最少取多少個數能保證人品最壞的情況下至少拿到P(P<1,000,000)分。
思路分析
因為RP總是很差，所以拿到被隱藏的數的時候是從最小開始拿的。如果每次都拿被隱藏的數的話，肯定是從小到大的一圈一圈的拿。
如果拿沒被隱藏的數的話，那么直接拿最大的就好了。
于是算法和去年上海regional第一題就一樣一樣了.... 前面要么一圈一圈拿被隱藏的數，要么都拿最大的數。
這個是貪心的。
最后P會剩一個余數。
暴力判斷是拿最大的還是拿被隱藏的(2選1，交叉著來是不可能的...)。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<vector>
5 #include<cstring>
6 using namespace std;
7 #define re(i,n) for(int i=0;i<n;i++)
8 #define re1(i,n) for(int i=1;i<=n;i++)
9 #define re2(i,n) for(int i=0;i<=n;i++)
10 #define re3(i,n) for(int i=1;i<n;i++)
11 #define clr(a,n) memset(a,n,sizeof(a))
12 template <typename T> inline T chkmin(T& a,T b){
return a > b ? a = b : a ; }
13 template <typename T> inline T chkmax(T& a,T b){
return a < b ? a = b : a ; }
14 int hash[100];
15 int cal(
int P,
int mx){
16 if(!mx)
return ~0u>>2;
17 return P/mx + (P%mx >0);
18 }
19 int cal(
int P,vector<
int> num){
20 sort(num.begin(),num.end());
21 int sum =0;
22 re(i,num.size()) {
23 sum+=num[i];
24 if(sum >= P)
return i+1;
25 }
26 return ~0u>>2;
27 }
28 class BlurredDartboard{
29 public :
30 int minThrows(vector <
int> num,
int P){
31 int n = num.size(),mx = 0;
32 re(i,n){
33 hash[num[i]] = 1;
34 chkmax(mx,num[i]);
35 }
36 vector <
int> temp;
37 re1(i,n)
if(!hash[i]) temp.push_back(i);
38 int m = temp.size(),suma = 0;
39 re(i,m) suma += temp[i];
40 if(!m) m = 1;
41 int sumb = mx*m;
42 int sum= max(suma,sumb);
43 int ans = P/sum*m;
44 cout<<ans<<endl;
45 P %=sum;
46 if(P==0)
return ans;
47 int a = cal(P,mx);
48 int b = cal(P,temp);
49 return ans + min(a,b);
50 }
51 };
52 550pt
有N(N<50)本書，每本書都有一個價值w[i]。現在有M次操作，每次操作i(i=0 mod 2)，小A可以從自己的書包拿出書向小B的書包里放最多move[i]本書。
每次操作j(j=0 mod 1)，小B可以從自己書包往小A書包里放最多move[j]本書。
第一次操作，小A要從書堆中拿出move[0]本書裝到B的書包中。
最后，小A的書包中書的總價值為Wa,小B為Wb。小A想讓Wb-Wa最大， 小B相讓Wa-Wb最大.
假設二個人都足夠聰明.... 輸出最后的Wa和Wb。
如果有多種選擇，那么輸出Wa+Wb最大的那種可能。
思路分析
沒敲完... 殘念啊... 我果然還是弱阿....
顯然除了第一步從書堆里放書意外，一旦書包中的書確定了，兩人都是貪心的拿書。
問題就是從書堆中拿哪些書...... DP就可以了吧....(ms有更簡單的？？)
update: 下午閑著沒事，就敲完了，可以去吃飯了(ms當時就是寫完了也進不了前50.... 還是弱 阿....)
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<cstring>
5 #include<vector>
6 using namespace std;
7 int hash[100];
8 void work(vector<
int> B,vector<
int> num){
9 vector<
int> A;
10 for(
int i=1; i< num.size();i++){
11 if(i&1){
12 sort(B.begin(),B.end());
13 int n = B.size();
14 int m = min(n,num[i]);
15 for(
int j = n-1; j>= n-m; j--){
16 A.push_back(B[j]);
17 B.erase((vector<
int>::iterator)&B[j]);
18 }
19 }
20 else {
21 sort(A.begin(),A.end());
22 int n = A.size();
23 int m = min(n,num[i]);
24 for(
int j = n-1; j>= n-m; j--){
25 B.push_back(A[j]);
26 A.erase((vector<
int>::iterator)&A[j]);
27 }
28 }
29 }
30 for(
int i=0;i<A.size();i++) hash[A[i]] = -1;
31 for(
int i=0;i<B.size();i++) hash[B[i]] = 1;
32 }
33 const int inf = ~0u>>2;
34 int dp[100][100],P[100][100];
35 class HeavyBooks{
36 public : vector <
int> findWeight(vector<
int> book,vector <
int> mv){
37 vector<
int> temp;
38 sort(book.begin(),book.end());
39 int n =book.size();
40 int m = min(mv[0],n);
41 for(
int i =0; i<m;i++) temp.push_back(i);
42 work(temp,mv);
43 // for(int i=0;i<m;i++) cout<<hash[i]<<" "; cout<<endl;
44 for(
int j=0;j<m;j++)
45 for(
int i=j;i<n;i++)
46 if(i == j){
47 P[i][j] = i-1;
48 dp[i][j] =(i ? dp[i-1][j-1]:0) + hash[j] * book[i];
49 }
50 else if(j == 0){
51 dp[i][0] = hash[0] * book[i];
52 P[i][0] = -1;
53 }
54 else {
55 int mx = -inf,s;
56 for(
int k = i-1; k>=j-1;k--)
57 if(dp[k][j-1] > mx){
58 s = k; mx = dp[k][j-1];
59 }
60 dp[i][j] = hash[j] * book[i] + mx;
61 P[i][j] = s;
62 }
63 int mx = -inf,s;
64 for(
int i=n-1; i>=m-1;i--)
65 if(dp[i][m-1]>mx){
66 s = i;
67 mx = dp[i][m-1];
68 }
69 int A = 0, B = 0;
70 for(
int i=m-1;i>=0;i--){
71 //cout<<s<<endl;
72 if(hash[i]>0) B += book[s];
else A += book[s];
73 s = P[s][i];
74 }
75 temp.clear();
76 temp.push_back(A);
77 temp.push_back(B);
78 return temp;
79 }
80 };
81 posted on 2012-05-13 08:47
西月弦 閱讀(395)
評論(0) 編輯 收藏 引用 所屬分類:
比賽感言