250pt
DP就可以了。。。
srm 558div1 275pt
1 #include<string>
2 #include<iostream>
3 using namespace std;
4 int dp[55][55][3];
5 int inf = ~0u>>2;
6 void update(int i ,int j,int c,int v){
7 int &ans = dp[i][j][c];
8 ans = min(dp[i-j][j][0],dp[i-j][j][1]);
9 ans = min(ans,dp[i-j][j][2]);
10 ans += v;
11 for(int p = i-j+1; p < i; p ++)
12 ans = min(ans,dp[p][j][c]+v);
13 }
14 class Stamp{
15 public : int getMinimumCost(string ch, int S, int C){
16 for(int i = 1; i<55;i++) for(int j = 0; j<55;j++) for(int p = 0;p <3; p++) dp[i][j][p]=inf;
17 for(int i = 1; i <= ch.size(); i++){
18 char match = '*'; bool flag = 1;
19 for(int j = 1; j <= i; j++){
20 if(!flag) continue;
21 if(ch[i-j] != '*' && match != '*' && ch[i-j] != match) {
22 //cout<< match<<" "<<ch[i-j]<<endl;
23 flag= 0;
24 }
25 else {
26 if(match == '*') match = ch[i-j];
27 if(match == '*' || match == 'R') update(i,j,0,C);
28 if(match == '*' || match == 'G') update(i,j,1,C);
29 if(match == '*' || match == 'B') update(i,j,2,C);
30 }
31 //cout<<i<<" "<<j<<" "<< dp[i][j][0] <<" "<<dp[i][j][1]<<" " <<dp[i][j][2]<<endl;
32 }
33 }
34 int ans = inf;
35 for(int i = 1; i <= ch.size(); i++) for(int p = 0; p < 3; p++)
36 ans = min(ans, dp[ch.size()][i][p] + S*i);
37 return ans;
38 }
39 };500pt
題目描述太復(fù)雜。。。 主要就是把紅色的點(diǎn)分四部分統(tǒng)計(jì)就可以了。。。
srm 558div1 550pt
1 #include<iostream>
2 #include<sstream>
3 #include<vector>
4 #include<string>
5 #include<algorithm>
6 #include<cmath>
7 using namespace std;
8 typedef long long ll;
9 const int inf = (int)1e5;
10 const double eps = 1e-9;
11 int find(vector<int> &num,int a,int b){
12 int y = upper_bound(num.begin(),num.end(),b) - num.begin();
13 int x = upper_bound(num.begin(),num.end(),a-1) - num.begin();
14 if(y-x < 0) return 0; return y-x;
15 }
16 void OP(vector<int>&num){for(int i=0;i<num.size();i++)cout<<num[i]<<" "; cout<<endl;}
17 class Ear{
18 public : ll getCount(vector <string> redX, vector <string> blueX, vector <string> blueY){
19 string rx,bx,by;
20 vector<int> redx,bluex,bluey;
21 for(int i = 0; i < redX.size(); ++i) rx += redX[i];
22 for(int i = 0; i < blueX.size(); ++i) bx += blueX[i];
23 for(int i = 0; i < blueY.size(); ++i) by += blueY[i];
24 stringstream sin(rx);
25 int val;
26 while(sin >> val) redx.push_back(val);
27 stringstream ain(bx);
28 while(ain >> val) bluex.push_back(val);
29 stringstream bin(by);
30 while(bin >> val) bluey.push_back(val);
31 sort(redx.begin(), redx.end());
32 int n = bluex.size(); ll ans = 0;
33 for(int i = 0; i < n; i++)
34 for(int j = 0; j < n; j++) if(bluey[i] > bluey[j]) {
35 int ux,dx,flag =0,x; double xx =bluex[j] + 1.0 * bluey[j] * (bluex[j] - bluex[i]) / (bluey[i] - bluey[j]);
36 //cout<<"pos: "<<bluey[i]<<" "<<bluey[j]<<" "<<xx<<endl;
37 if(bluey[j] * (bluex[j] - bluex[i]) % (bluey[i] - bluey[j]) == 0) {
38 flag = 1; x = (int)xx;
39 }
40 ux = ceil(xx-eps);
41 dx = floor(xx+eps);
42 ll a,b,c,d;
43 if(bluex[j] >= bluex[i]) {
44 d = find(redx,bluex[i],bluex[j]-1);
45 c = find(redx,-1,bluex[i]-1);
46 if(flag) ux = x+1, dx = x;
47 a = find(redx,ux,inf);
48 b = find(redx,bluex[j]+1,dx);
49 }
50 else {
51 d = find(redx,bluex[j]+1,bluex[i]);
52 c = find(redx,bluex[i]+1,inf);
53 if(flag) ux = x, dx = x-1;
54 a = find(redx,-1,dx);
55 b = find(redx,ux,bluex[j]-1);
56 }
57 ans += (c*(c-1)/2 + c * d) *( a*(a-1)/2 + a*b);
58 //cout<< "ans : "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<ans<<endl;
59 }
60 return ans;
61 }
62 };
posted on 2012-10-24 16:22
西月弦 閱讀(246)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告