算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
300pt
   一个串S是由X和Y在不改变本身字母相对顺序的情况下拼成的。其中Y是X的一个排列,求字典序最小的Y。

算法分析:
   贪心构造。
 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
   一个环形序列{(ai, di)},每次选择一个j,让j ... j+aj的所有数都从序列中删除(是环形的哦~)。得分为dj,如果剩下的数不足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 西月弦 阅读(587) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理