涨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
西月弦 阅读(484)
评论(0) 编辑 收藏 引用 所属分类:
解题报告 、
比赛感言