涨了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
西月弦 阅读(387)
评论(0) 编辑 收藏 引用 所属分类:
比赛感言