算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
涨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 西月弦 阅读(442) 评论(0)  编辑 收藏 引用 所属分类: 解题报告比赛感言

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