A题
分两部分求，因为题目数只有15，所以可以2^15枚举分组情况(分给L还是分给M)。
接下来求对于同一size的M种颜色的气球分配给N个题目的最小代价。
排序之后，从大到小贪心的分配就可以了。
1 #include<iostream>
2 #include<string>
3 #include<vector>
4 using namespace std;
5 const int inf = ~0u>>2;
6 int make(vector<int> &flag, vector<int> &num){
7 int n = num.size(), m = flag.size(),len = min(n,m);
8 int suma = 0, sumb = 0;
9 for(int i = 0; i < n; i++) suma += num[i];
10 for(int i = 0; i < m; i++) sumb += flag[i];
11 if(suma > sumb) return inf;
12 for(int i = 0; i < len; i++) suma -= min(num[i],flag[i]);
13 return suma;
14 }
15 bool cmp(int a,int b){return a>b;}
16 void op(vector<int> s){
17 for(int i = 0; i < s.size(); i++)cout<<s[i]<<" ";cout<<endl;
18 }
19 class ICPCBalloons{
20 public :
21 int minRepaintings(vector <int> bC, string bS, vector <int> num){
22 int n= num.size();
23 vector<int> M ,L;
24 for(int i =0; i < bS.size(); i++) if(bS[i] == 'L') L.push_back(bC[i]); else M.push_back(bC[i]);
25 sort(M.begin(),M.end(),cmp);
26 sort(L.begin(),L.end(),cmp);
27 sort(num.begin(),num.end(),cmp);
28 cout<<"M: "<<endl; op(M);
29 cout<<"L: "<<endl; op(L);
30 int ans = inf;
31 for(int i = 0; i < (1<<n); i++) {
32 vector<int> m,l;
33 for(int j = 0; j < n; j++) if(1<<j & i) m.push_back(num[j]); else l.push_back(num[j]);
34 int a = make(M,m);
35 int b = make(L,l);
36 //cout<<"m: "<<endl; op(m);
37 //cout<<"l: "<<endl; op(l);
38 ans = min(ans,a+b);
39 }
40 return ans == inf ? -1 : ans;
41 }
42 };
B题
博弈，给若干个有根树，节点数不超过50，两个人轮流给某个未染色的点染色，这个点一旦被染色，它以及它的所有祖先就都被染色了。
问先手胜还是后手胜。
树形DP求SG值，复杂度O(n^3)。非常裸...
更大规模的解法见
http://www.2333333.tk/182.html
#include<string>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int N = 55;
int P[N] ,n, dp[N];
vector<int> G[N];
inline void setc(int p,int c){P[c] = p;
G[p].push_back(c);
}
bool ispar(int s,int p){
while(s!=-1){if(s==p)return 1; s=P[s];} return 0;
}
int dfs(int u) {
// cout<<"u; "<<u<<endl;
int &ans = dp[u];
if(ans != -1) {
//cout<<"back"<<endl;
return ans;
}
bool vis[101] = {0};
for(int i = 0; i < n; i++) if(ispar(i,u)) {
// cout<<"i: "<<i<<endl;
int v = i, last = -1 ,sg = 0;
while(v != P[u]) {
for(int j = 0; j < G[v].size(); j ++) if(G[v][j] != last) sg ^= dfs(G[v][j]);
last = v;
v = P[v];
}
vis[sg] = 1;
}
for(int i = 0; i < 101; i++) if(!vis[i]) {ans = i; break;}
//cout<<"back"<<endl;
return ans;
}
double dis(int x0,int y0,int x1,int y1){return sqrt(1.0*(x0-x1)*(x0-x1) + 1.0*(y0-y1)*(y0-y1));}
class CirclesGame{
public:
string whoCanWin(vector <int> x, vector <int> y, vector <int> r){
memset(P,-1,sizeof(P));
memset(dp,-1,sizeof(dp));
n = x.size();
for(int i =0 ; i < n; i++) {
int s = -1;
for(int j= 0; j < n; j++) if(j != i && 1.0*(r[j] - r[i]) > dis(x[i],y[i],x[j],y[j])){
//cout<<j<<" "<<i<<" "<<r[j]-r[i]<<" "<<dis(x[i],y[i],x[j],y[j])<<endl;
if(s == -1 || r[j] < r[s]) s = j;
}
if(s != -1){
setc(s,i);
}
}
//cout<<"endl"<<endl;
// for(int i = 0; i < n; i++) cout<<P[i]<<" ";cout<<endl;
int ans = 0;
for(int i = 0; i < n; i++) if(-1 == P[i]) ans ^= dfs(i);
return ans ? "Alice" : "Bob";
}
};
posted on 2012-11-21 16:02
西月弦 阅读(506)
评论(3) 编辑 收藏 引用 所属分类:
解题报告