漲18rating.....
250pt
一個只含有大寫字母的長度為N的字符串，問交換相鄰字母X次后，最長的連續字母是多長。(N<50,X<2,500)
算法分析：
枚舉，枚舉再枚舉。 枚舉字母的“集結點”，然后模擬。O(N*N*X)。 尼瑪我居然枚舉的聯通塊什么水平。。。。。還交了兩次98pt...
#include<string>
#include<cstdlib>
#include<iostream>
using namespace std;
int vis[100];
inline bool dis(int l,int r,int pos,int &mx){
int v = min(abs(pos-l),abs(pos-r))-1;
if(v < mx) {mx = v; return 1;}
return 0;
}
const int inf = ~0u>>2;
class ColorfulChocolates{
public : int maximumSpread(string ch, int ms){
int n = ch.size(), ans = 0;
for(int i=0;i<26;i++){
char x = 'A'+i;
bool flag = 0;
int l,r, v = 0;
for(int i=0;i<n;i++) {
if(ch[i]==x) {
if(!flag) l = i, flag = 1;
}
//cout<<"i: "<<i<<" "<<l<<endl;
int value =0;
// block
if(flag && (i == n-1 || ch[i+1]!=x)){
// cout<<"l: "<<l<<" "<<r<<endl;
flag = 0; r = i;
int tp = ms;
for(int i=0;i<n;i++) vis[i] = 0;
value = r-l+1;
while(1){
int mx = inf,s=-1;
for(int j=0;j<n;j++)
if(j < l || j> r)
if(!vis[j]&&ch[j]==x && dis(l,r,j,mx)) {
// cout<<j<<" ";
s = j;
}
cout<<endl;
if(s==-1) break;
if(mx > tp) break;
tp -= mx; vis[s] = 1;
if(s > r) r ++; else l--;
value ++;
// cout<<s<<" "<<mx<<" "<<tp<<endl;
}
// cout<<l<<" "<<r<<" "<<value<<endl;
}
if(value > v) v = value;
}
// cout<<x<<" "<<v<<endl;
if(ans<v) ans = v;
}
return ans;
}
};
500pt
一個N<50個點的有向圖，你一開始再結點1，每次只能走相鄰的且標號最小的結點。問最少切割多少個點，才可能到達點N-1。
算法分析：
這是個從后往前的動態規劃，dp[i]代表從i到n-1最少切割的點數。它可以從它能到達的點推導而來。
最優解沒有環，且轉移順序不明確。典型的spfa可搞。
#include<iostream>
#include<string>
#include<vector>
using namespace std;
const int N = 55;
int dp[N], vis[N], Q[N*N*N];
const int inf = ~0u>>2;
bool relax(int c,int &d){
if(c<d){d = c; return 1;}
return 0;
}
class ColorfulWolves{
public :int getmin(vector<string> G){
int n = G.size();
for(int i=0;i<n;i++) dp[i] = inf;
Q[0] = n-1;
dp[n-1] = 0;
int head= 0,tail = 1;
while(head<tail){
int u = Q[head++]; vis[u] = 0;
for(int v = 0; v< n; v++) if(G[v][u] == 'Y'){
int cnt =0;
for(int i=0;i<u;i++) cnt += G[v][i] =='Y';
if(relax(cnt+dp[u],dp[v]) && !vis[v]){
vis[v] = 1;
Q[tail++] = v;
}
}
}
return dp[0] == inf? -1: dp[0];
}};
posted on 2012-08-05 09:50
西月弦 閱讀(511)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告 、
比賽感言