吐槽：
无力吐槽了，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
西月弦 阅读(427)
评论(0) 编辑 收藏 引用