吐槽：
無力吐槽了，450pt怎么那么難。。。
250pt
題目意思是，有N（N<=50）個數，每個數的可變范圍是[max(N-X,1),N+X]。讓這個數列嚴格遞增的最小X是多殺？
算法分析：
二分枚舉答案然后貪心判定。每個數都盡可能的小。
1 #include<vector>
2 #include<iostream>
3 using namespace std;
4 class KingdomAndTrees{
5 public : int minLevel(vector <int> num){
6 int n = num.size();
7 int l = 0, r = 1000000000;
8 while(l<r){
9 int mid = l+r >>1;
10 int pre = 0, flag = 1;
11 // cout<<l<<" "<<r<<" "<<mid<<endl;
12 for(int i=0;i<n;i++){
13 if(num[i] + mid <= pre){ flag = 0; break; }
14 pre = max(pre+1, num[i] - mid);
15 // if(mid == 5) cout<< pre<<" ";
16 }
17 if(flag) r = mid; else l = mid+1;
18 }
19 return l;
20 }
21 };
450pt
有兩個N<50個面的骰子，每個面的數字是1-X的唯一某個數。第一個骰子有些面是0。現在兩個骰子同時投擲，請你把第一個骰子某些為0的面寫上一些唯一的1-X的數字，讓第一個骰子的勝率盡可能接近0.5。
算法分析：
等同于求，有一大堆數[1,X]。有N個空格，讓你求在某些空格上寫一些數，最后可以勝利的所有可能。
背包模型，動規求解。DP[i][j][k]，表示前i個骰子，填入前j個空格，是否可能贏k次。用0-1背包的寫法，可以省一唯空間。
1 #include<vector>
2 #include<algorithm>
3 #include<iostream>
4 using namespace std;
5 bool dp[55][2555];
6 class KingdomAndDice{
7 public :
double newFairness(vector <
int> fD, vector <
int> sD,
int X){
8 int now = 0, len = 0, n = sD.size();
9 for(
int i=0;i<n; i++){
10 len += fD[i] == 0;
11 for(
int j=0; j<n; j++)
12 now += fD[i] > sD[j];
13 }
14 sort(sD.begin(), sD.end());
15 int mx = n*n;
16 for(
int i=0;i<=len; i++) dp[i][now] = 1;
17 for(
int i=0;i<n;i++){
18 int l = sD[i] + 1;
19 int r = i== n-1 ? X : sD[i+1] - 1;
20 int cnt = r - l + 1;
21 for(
int j=0; j<n; j++)
if(fD[j] >=l && fD[j] <= r) cnt --;
22 cnt = min(cnt, len);
23 for(
int j=0; j< cnt; j++)
24 for(
int k = len-1;k >=0; k--)
25 for(
int p = 0; p <= mx; p++)
26 if(dp[k][p] && p + i + 1 <= mx){
27 dp[k+1][p + i + 1] = 1;
28 }
29 }
30 int m = abs(n*n ), ans = now;
31 for(
int p = 0; p <=mx; p++){
32 for(
int i=0; i<=len; i++) {
33 if(dp[i][p] && abs(n*n-p*2) < m){
34 ans = p; m = abs(n*n-p*2);
35 }
36 }
37 }
38 return 1.0*ans/mx;
39 }
40 };
posted on 2012-07-04 12:05
西月弦 閱讀(438)
評論(0) 編輯 收藏 引用