Description
現有k個串，一個目標串，你從這k個字符串中選取一些字符，組成目標串。現有的k個串中每個串至多可選ai個字符，
而且從第i個串中選取
一個字符耗費i個金幣，求組成目標串所消耗最小的金幣數，如果不能組成，輸出-1；
Input
第一行是目標串，第二行一個k（0<k<=100）,接下來k行，每行包括一個現有串，和ai(所有字符串長度不超過100，且非空)
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 <queue>
#include <cstdio>
#include <cstring>
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<int> 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; //總流量
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)
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<L;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<len;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;
}
逆序對
TimeLimit: 1 Second MemoryLimit: 32 Megabyte
Totalsubmit: 20 Accepted: 4
Description
逆序對大家都知道，對于1-n的任意一個排列：a1,a2,a3...an，如果 存在i<j，且ai>aj，則(i,j)稱之為一對逆序對。我們常常關心一個排列的逆序對的總數，因為它可以反映一個排列的有序程度。現在 LAM想知道,在1-n的所有排列中，有多少排列的逆序對總數恰好為k。
Input
第一行為正整數T,表示數據組數，接下來T行，每行兩個正整數:n,k(n,k<=1000)。
Output
對于每個輸入，輸出一行表示恰好為k的排列的個數。由于數字可能較大，只需要輸出mod10000的結果即可。
Sample Input
1
4 1
Sample Output
3
Source
lrl
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
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;
}