300pt
一個串S是由X和Y在不改變本身字母相對順序的情況下拼成的。其中Y是X的一個排列，求字典序最小的Y。
算法分析：
貪心構(gòu)造。
1 #include<iostream>
2 #include<
string>
3 using namespace std;
4 bool vis[55];
5 int hash[55],tmp[55];
6 class 7 FoxAndHandle{
8 public :
string lexSmallestName(
string ch){
9 int n = ch.size();
10 for(
int i =0; i < n; i++)
11 hash[ch[i] -'a'] ++;
12 int cnt[55];
13 for(
int i = 0; i < 26; i++){
14 hash[i]/= 2;
15 cnt[i] = hash[i];
16 }
17 string ans;
18 int now = 0;
19 for(
int _=0;_<n/2;_++){
20 for(
int i = 0; i < 26; i++)
if(cnt[i]){
21 bool flag = 0;
22 for(
int j = now; j < n; j++){
23 if(ch[j] == i+'a') {
24 flag = 1;
25 memset(tmp,0,
sizeof(tmp));
26 for(
int p = 0; p < j; p++)
if(!vis[p]){
27 int x = ch[p] - 'a';
28 tmp[x] ++;
29 cout<<p<<" "<<x<<" "<<tmp[x]<<" "<<hash[x]<<endl;
30 if(tmp[x] > hash[x]) {flag = 0;
break;}
31 }
32 cout<<"chk: "<<_<<" "<<j<<" "<<i<<" "<<flag<<endl;
33 if(flag) {vis[j] = 1; ans+=ch[j]; now = j+1;}
34 break;
35 }
36 }
37 if(flag) {cnt[i] --;
break;}
38 }
39 }
40 return ans;
41 }
42 };
500pt
一個環(huán)形序列｛(ai, di)｝，每次選擇一個j，讓j ... j+aj的所有數(shù)都從序列中刪除(是環(huán)形的哦～)。得分為dj，如果剩下的數(shù)不足aj，就不能選它。
求可以得到的最大得分總和。
算法分析：
因為任意一個沒有順序的sum(a)<=n的方案都是合法的(否則會大于n)。那么這就等價于一個01背包問題了，果然tc就是拼YY啊...
1 #include<iostream>
2 #include<cstring>
3 #include<vector>
4 using namespace std;
5 const int inf = (int)1e9;
6 int dp[55*55];
7 int work(vector<int> a,vector <int> d){
8 int n = a.size(), ans = 0;
9 memset(dp,-1,sizeof(dp));
10 dp[0] = 0;
11 for(int j = 0; j < n; j++){
12 for(int i = n+1; i; i--) if(i - a[j] >= 0 ){
13 int v = i - a[j];
14 if(dp[v] == -1) continue;
15 dp[i] = max(dp[i],dp[v] + d[j]);
16 //cout<<i<<" "<<dp[i]<<endl;
17 ans = max(ans,dp[i]);
18 }
19 // cout<<endl;
20 }
21 return ans;
22 }
23 class SpellCards{
24 public : int maxDamage(vector <int> level, vector <int> damage){
25 return work(level,damage);
26 }
27 };
28
posted on 2012-12-09 03:17
西月弦 閱讀(625)
評論(0) 編輯 收藏 引用