亚洲免费视频网站,野花国产精品入口,中文欧美字幕免费

lenohoo — Sat, 10 Nov 2012 13:44:00 GMT

KMP

TimeLimit: 1 Second MemoryLimit: 32 Megabyte

Totalsubmit: 2 Accepted: 1

Description

现有k个串�Q�一个目标串�Q�你从这k个字�W�串中选取一些字�W�，�l�成目标丌Ӏ�现有的k个串中每个串臛_��可选ai个字�W�，
而且从第i个串中选取
一个字�W�耗费i个金币，求组成目标串所消耗最��的金币敎ͼ�如果不能�l�成�Q�输�?1�Q?br />

Input

�W�一行是目标�Ԍ��W�二行一个k�Q?

Output

最��消耗的金币

Sample Input

zhonghongyihelafeng
5
zhonghongyihenshuai 10
zhonghongyihennx 10
zhonghongyihenyingjun 10
chuxinggedadiaosi 10
wobuxihuanheichuxing 10
bbaze
3
bzb 2
aeb 3
ba 10

Sample Output

-1
8

Source

zhy

#include
#include
#include
using namespace std;
#define MAXN 1010
#define MAXM 1000200
#define INF (1<<29)
int sumFlow;
struct Edge{
    int u,v,cap,cost;
    int next;
}edge[MAXM<<2];
int NE;
int head[MAXN],dist[MAXN],pp[MAXN];
bool vis[MAXN];
char ch[MAXN] ;
int k , n;
void init(){
    NE = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost){
    edge[NE].u=u;edge[NE].v=v;edge[NE].cap=cap;edge[NE].cost=cost;
    edge[NE].next=head[u];head[u]=NE++;
    edge[NE].u=v;edge[NE].v=u;edge[NE].cap=0;edge[NE].cost=-cost;
    edge[NE].next=head[v];head[v]=NE++;
}
bool SPFA(int s,int t,int n){
    int i,u,v;
    queue qu;
    memset(vis,0,sizeof(vis));
    memset(pp,-1,sizeof(pp));
    for(i=0;i<=n;i++) dist[i]=INF;
    vis[s]=1;dist[s]=0;
    qu.push(s);
    while(!qu.empty()){
        u=qu.front();qu.pop();vis[u]=0;
        for(i=head[u];i!=-1;i=edge[i].next){
            v=edge[i].v;
            if(edge[i].cap && dist[v]>dist[u]+edge[i].cost){
                dist[v]=dist[u]+edge[i].cost;
                pp[v]=i;
                if(!vis[v]){
                    qu.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    if(dist[t]==INF) return false;
    return true;
}
int MCMF(int s,int t,int n){//最��费用最大流
    int flow = 0;    //��L��?br />    int i,minflow,mincost;
    mincost = 0;
    while(SPFA(s,t,n)){
        minflow = INF+1;
        for(i=pp[t];i!=-1;i=pp[edge[i].u])
            if(edge[i].cap                minflow = edge[i].cap;
        flow+=minflow;
        for(i=pp[t];i!=-1;i=pp[edge[i].u]){
            edge[i].cap-=minflow;
            edge[i^1].cap+=minflow;
        }
        mincost += dist[t]*minflow;
    }
    sumFlow = flow;//最大流
    return mincost;
}
int C[33] , cnt[33] , a[111];
int main() {
    while(~scanf("%s",ch)) {
        int L = strlen(ch);
        memset(C,0,sizeof(C));
        for(int i=0;i            int aa = ch[i] - 'a';
            C[aa] ++;
        }
        scanf("%d",&k);
        n = 27 * k + 30;
        int s = 27 * k + 28 , t = 27 * k + 29;
        init();
        for(int i=0;i<26;i++) if(C[i]) addedge(s,i,C[i],0);
        for(int i=1;i<=k;i++) {
            for(int j=0;j<26;j++) {
                if(C[j]) addedge(j,i*27+j,C[j],0);
            }
            scanf("%s",ch);
            scanf("%d",&a[i]);
            int len = strlen(ch);
            memset(cnt,0,sizeof(cnt));
            for(int j=0;j                int aa = ch[j] - 'a';
                cnt[aa] ++;
            }
            for(int j=0;j<26;j++) {
                if(cnt[j]) {
                    addedge(27*i+j,27*i+26,cnt[j],0);
                }
                //printf("a[i] is %d\n",a[i]);
            }
            addedge(27*i+26,t,a[i],i);
        }
        int ans = MCMF(s,t,n);
        if(sumFlow == L) printf("%d\n",ans);
        else printf("-1\n");
        //printf("default : sumFlow is %d , mincost is %d \n",sumFlow,ans);
    }
    return 0;
}

逆序�?/p>

TimeLimit: 1 Second MemoryLimit: 32 Megabyte

Totalsubmit: 20 Accepted: 4

Description

逆序对大安��知道�Q�对�?-n的�Q意一个排列：a1,a2,a3...an�Q�如�?存在iaj�Q�则(i,j)�U�C��Z��寚w��序寏V��我们常常关心一个排列的逆序对的��L��Q�因为它可以反映一个排列的有序�E�度。现�?LAM想知�?�?-n的所有排列中�Q�有多少排列的逆序�Ҏ(gu��)��L��恰好为k�?br />

Input

�W�一行�ؓ正整数T,表示数据�l�数�Q�接下来T行，每行两个正整�?n,k(n,k<=1000)�?br />

Output

对于每个输入�Q�输��Z��行表�C�恰好�ؓk的排列的个数。由于数字可能较大，只需要输出mod10000的结果即可�?br />

Sample Input

1
4 1

Sample Output

Source

lrl

#include
#include
#include
#include
using namespace std;
int f[1010][1010];
int sum[1010][1010];
int n , k , T;
int S(int nn , int kk) {
    if(kk<0) return 0;
    else return sum[nn][kk] % 10000;
}
void init() {
    for(int i=1;i<=1000;i++) f[i][0] = sum[i][0] = 1;
    for(int i=1;i<=1000;i++)
    for(int j=1;j<=1000;j++) {
        f[i][j] = (S(i-1,j) - S(i-1,j-i)) % 10000;
        while(f[i][j] < 0) f[i][j] += 10000;
        sum[i][j] = ( sum[i][j-1] + f[i][j] ) % 10000;
    }
}
int main() {
    init();
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&k);
        printf("%d\n",f[n][k]);
    }
    return 0;
}

lenohoo 2012-11-10 21:44 发表评论

lenohoo — Mon, 15 Oct 2012 13:04:00 GMT

转自��yai
把b[][]数组上的每个位拆开成两个点i和i'�Q�（不超�q?2位）�Q�另外新加两个点0�?,如果��定某点i对应的是0,则i�?点合�qӞ��i'点与1点合�qӞ��如果��定某点i对应的是1,则i�?合�ƈ�Q�i'�?合�ƈ�Q�如果确定两点i和j对应的位是相反的�?则i与j'合�ƈ�Q�j与i'合�ƈ�Q�如果确定两点对应的位是相同的数�Q�则i与j合�ƈ�Q�i'与j'合�ƈ�?br />最�q�比较忙�Q�所以题解比较水�Q�所以具体还是看代码吧�?br />因�ؓ要空出数�l?点和1点，所以我�?到n而不是从0到n-1,所以奇偶性的判断要换一下�?br />#include
#include
#include
#include
using namespace std;
const int maxn = 100000;
int p[maxn];
int b[505][505];
int n;
void init() {
    for(int i=0;i<(2*n+1)*32+100;i++) p[i] = i;
}
int find(int x) {
    return x==p[x] ? x : p[x] = find(p[x]);
}
void Union(int x,int y) {
    int a = find(x) , b = find(y);
    p[a] = p[b] = p[x] = p[y] = min(a , b);
}
bool check() {
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++)
            if(b[i][j] != b[j][i]) return 0;
        if(b[i][i] != 0) return 0;
    }
    init();
    int m = 32 * n;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++) {
            if(i % 2 == 0 && j % 2 == 0) {
                for(int k=0;k<32;k++) {
                    if(b[i][j] & (1<                        int u = i*32+k , v = j*32+k;
                        if(find(u) == find(1) || find(v) == find(1) || find(u) == find(v+m)) return 0;
                        Union(u,0);
                        Union(v,0);
                        Union(u+m,1);
                        Union(v+m,1);
                    }
                }
            }
            else if(i % 2 == 1 && j % 2 == 1) {
                for(int k=0;k<32;k++) {
                    if(b[i][j] & (1<                        int u = i* 32 + k , v = j*32+k;
                        if(find(u) == find(0) || find(v)==find(0) || find(u) == find(v+m)) return 0;
                        Union(u,1);
                        Union(v,1);
                        Union(u+m,0);
                        Union(v+m,0);
                    }
                }
            }
            else {
                for(int k=0;k<32;k++) {
                    int u = i * 32 + k , v = j * 32 + k;
                    if(b[i][j] & (1<                        if(find(u) == find(v)) return 0;
                        Union(u,v+m);
                        Union(u+m,v);
                    }
                    else {
                        if(find(u) == find(v+m)) return 0;
                        Union(u,v);
                        Union(u+m,v+m);
                    }
                }
            }
        }
    return 1;
}
int main() {
    while(~scanf("%d",&n)) {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&b[i][j]);
        if(check()) puts("YES");
        else puts("NO");
    }
    return 0;
}

lenohoo 2012-10-15 21:04 发表评论

差分�U�束�pȝ��

lenohoo — Thu, 17 May 2012 03:52:00 GMT

b - a < = c <==> add_edge(a - > b , c)

限制条�g�?b和a之间有一�?距离臛_��?c �?�?�Q�就�?从a �?b �q�一�?c �?img src ="http://m.shnenglu.com/lenohoo/aggbug/175186.html" width = "1" height = "1" />

lenohoo 2012-05-17 11:52 发表评论