lemonoil

OI__nothing is impossible

最短路---NOI

• 标签: 最短路 NOI

最短路径(shortest)

256MB 1seconds 【题目描述】 给定无向图，包含n个顶点，m条无向边，边上有权值。从1号点出发不经过i号点到达n号点的最短路径计作di，求d2..dn-1。 【输入格式】 第一行两个正整数n，m，表示点的数量和边的数量。 随后m行，每行三个正整数x、y、z，表示x到y的边权值为z。 【输出格式】 仅一行，包含n-2个整数，依次为d2..dn-1。 【输入样例】 4 4 1 2 1 1 3 1 2 4 2 3 4 1 【输出样例】 2 3 【数据规模与约定】 对于100%的数据，n, m<=200000。

题解

如果考试的话，我绝壁写个SPFA大暴力，最多改写手写循环队列，了事。orz wxh大佬。。。。 自己的大暴力。。。。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<stack>
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define res(i,x,y) for(int i=x;i<=y;i++)
#define INF 2100000000
#define ll long long
#define clr(x)  memset(x,0,sizeof(x))
#define NAME "ans"
using namespace std;
inline int readin(){
	static char ch;int res,flag=1;
	while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
	while((ch=getchar())<='9'&&ch>='0')res=ch-48+res*10;res*=flag;
	return res;
}
int n,m;
struct Edge{
	int from,to,dist;
	Edge(int u,int v,int d):from(u),to(v),dist(d){}
};
const int maxn = 200000;
struct SPFA{
	int n,m;
	vector<Edge> edges;
	vector<int> G[maxn];
	bool done[maxn];
	int d[maxn];
	int p[maxn];
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++)G[i].clear();
		edges.clear();
	}
	void AddEdge(int from,int to,int dist){
		edges.push_back(Edge(from,to,dist));
		m=edges.size();
		G[from].push_back(m-1);
	}
	void AddDedge(int from,int to,int dist){
		edges.push_back(Edge(from,to,dist));
		m=edges.size();
		G[from].push_back(m-1);
		edges.push_back(Edge(dist,to,from));
		m=edges.size();
		G[dist].push_back(m-1);
	}
	void spfa(int s){
		queue<int> Q;
		memset(done,0,sizeof(done));	
		for(int i=0;i<n;i++)d[i]=INF;
		d[s]=0;
		done[s]=1;
		Q.push(s);
		while(!Q.empty()){
			int u=Q.front();Q.pop();
			done[u]=0;
			for(register int i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(d[u]<INF&&d[e.to]>d[u]+e.dist){
					d[e.to]=d[u]+e.dist;
					p[e.to]=G[u][i];
					if(!done[e.to]){
						Q.push(e.to);
						done[e.to]=1;
					}
				}
			}
		}
	}
	void spfas(int s){
		queue<int> Q;
		memset(done,0,sizeof(done));	
		for(register int i=0;i<=n;i++)d[i]=INF;
		d[1]=0;
		done[1]=1;
		Q.push(1);
		while(!Q.empty()){
			int u=Q.front();Q.pop();
			done[u]=0;
			for(register int i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(e.to!=s&&d[u]<INF&&d[e.to]>d[u]+e.dist){
					d[e.to]=d[u]+e.dist;
					p[e.to]=G[u][i];
					if(!done[e.to]){
						Q.push(e.to);
						done[e.to]=1;
					}
				}
			}
		}
	}
};
SPFA slover;
int main(){
	freopen(NAME".in","r",stdin);
	freopen(NAME".out","w",stdout);
	n=readin(),m=readin();
	slover.init(n);
	for(register int i=1;i<=m;i++)
		slover.AddDedge(readin(),readin(),readin());
	for(register int i=2;i<n;i++)
		slover.spfas(i),cout<<slover.d[n]<<' ';
	return 0;
}

fastest正解 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<cstdio>
#include<queue>
#include<algorithm>
#define maxn 200100
#define lld long long
using namespace std;
const lld inf = 1e18;
struct edge{
	int u,np,next,va;
	bool mark;
}e[maxn*2];
int head[maxn];
int e_cnt = 1;
inline void add_e(int u,int v,int va){
	e[++e_cnt] = (edge){u,v,head[u],va,0};
	head[u] = e_cnt;
	e[++e_cnt] = (edge){v,u,head[v],va,0};
	head[v] = e_cnt;
}
int n,m;
lld dis[maxn],dis_n[2][maxn];
int ide[maxn];
bool inq[maxn];
queue<int> qx;
int co[maxn],co_mx;
int fa[maxn];
lld anss[maxn];
bool isva[maxn];
inline void dfs(int x){
	for(int ne = head[x];ne;ne = e[ne].next){
		if(!e[ne].mark || e[ne].np == fa[x]) continue;
		fa[e[ne].np] = x;
		if(!co[e[ne].np]) co[e[ne].np] = co[x];
		dfs(e[ne].np);
	}
}
struct dat{
	int l,r;
	lld va;
	bool operator < (const dat& x) const{
		return va < x.va;
	}
}dt[maxn];
int dt_ct = 0;
int pre[maxn];
inline int getp(int x){
	return x == pre[x]?x:(pre[x]=getp(pre[x]));
}
inline void solve(){
	for(int i = 1;i<=n;++i) anss[i] = dis_n[0][i] = dis_n[1][i] = dis[i] = inf;
	dis[1] = 0;
	qx.push(1);
	while(!qx.empty()){
		int now = qx.front();
		qx.pop();
		inq[now] = 0;
		for(int ne = head[now];ne;ne = e[ne].next){
			int cur = e[ne].np;
			if(dis[cur] > dis[now] + e[ne].va){
				dis[cur] = dis[now] + e[ne].va;
				ide[cur] = ne;
				if(!inq[cur]) inq[cur]=1,qx.push(cur);
			}
		}
	}
	co_mx = 0;
	for(int k = ide[n];k;k = ide[e[k].u]) ++co_mx;
	co[n] = co_mx+1;
	for(int k = ide[n];k;k = ide[e[k].u]) isva[e[k].u] = 1,co[e[k].u] = co_mx--;
	co_mx = co[n];
	for(int i = 2;i <= n;++i) e[ide[i]].mark = e[ide[i] ^ 1].mark = 1;	
	dfs(1);
	dis_n[0][n] = 0;
	qx.push(n);
	while(!qx.empty()){
		int now = qx.front();
		qx.pop();
		inq[now] = 0;
		for(int ne = head[now];ne;ne=e[ne].next){
			int cur = e[ne].np;
			bool fg = 0;
			if(dis_n[0][cur] > dis_n[0][now] + e[ne].va){
				dis_n[0][cur] = dis_n[0][now] + e[ne].va;
				fg = 1;
			}
			if(!isva[cur]){
				if(co[cur] == co[now]){
					if(dis_n[1][cur] > dis_n[1][now] + e[ne].va){
						dis_n[1][cur] = dis_n[1][now] + e[ne].va;
						fg = 1;
					}
				}
				else if(co[cur] < co[now]){
					if(dis_n[1][cur] > dis_n[0][now] + e[ne].va){
						dis_n[1][cur] = dis_n[0][now] + e[ne].va;
						fg = 1;
					}
				}
			}
			if(fg && !inq[cur]) inq[cur] = 1,qx.push(cur);
		}
	}
	dis_n[1][n] = 0;
	for(int i = 2;i <= e_cnt;++i){
		if(e[i].mark) continue;
		int u = e[i].u,v = e[i].np,va = e[i].va;
		if(co[u]+1 <= co[v]-1) dt[++dt_ct] = (dat){co[u]+1,co[v]-1,dis_n[0][v]+va+dis[u]};
		if(co[u]+1 <= co[v]) anss[co[v]] = min(anss[co[v]],dis_n[1][v]+va+dis[u]);
	}
	for(int i = 1;i<=co_mx+1;++i) pre[i] = i;
	sort(dt+1,dt+1+dt_ct);
	for(int i = 1;i<=dt_ct;++i){
		int l = dt[i].l,r = dt[i].r;
		for(int nxt = getp(l);nxt <= r;){
			anss[nxt] = min(anss[nxt],dt[i].va);
			pre[nxt] = nxt+1;
			nxt = getp(nxt+1);
		}
	}
	for(int i = 2;i <= n-1;++i){
		if(!isva[i]) printf("%lld ",dis[n]);
		else printf("%lld ",anss[co[i]]);
	}
}
int a1,a2,a3;
int main(){
	freopen("shortest.in","r",stdin);
	freopen("shortest.ans","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i<=m;++i){
		scanf("%d%d%d",&a1,&a2,&a3);
		add_e(a1,a2,a3);
	}
	solve();
	return 0;
}

第一视角(blind)

【问题描述】 QQ：我来给你出道题！给定一个有向图，包含n个点（编号1至n）和m条边，求1号点到2号点的最短路。 你：这个问题太简单了，…… QQ：我们增加一些难度，这m条边中有一条指定的边坏掉了，它不能经过。问这种情况下1号点到2号点的最短路。 你：直接把坏掉的那条边删掉，然后再求最短路不就好了。问题似乎没有变难呀！ QQ：这是由于你开了“上帝视角”，你知道哪条边是坏的，当然简单了！如果你是以“第一视角”去寻找最短路，换句话讲，最初你并不知道哪条边是坏的，只有走到“坏边”的起点后，才知道这条边是不能通过的。这种情况下，你要从1号点走到2号点，最少要走多少距离呀。 你：那当然要看是哪条边坏掉啦！不同的边坏掉答案是不一样的。 QQ：那……你帮我算算，最坏情况下需要走多远。 你：好的！马上就去写程序！ 【输入格式】 第一行包含两个正整数n、m，分别表示点数和边数。 随后m行，每行三个正整数x、y、w，表示有一条从x到y的有向边，距离为w。 【输出格式】 仅一行，包含一个正整数，表示最坏情况下需要走多少距离。若不能到达，输出-1。 【样例输入】 4 6 1 3 1 1 4 1 3 1 5 4 1 10 3 2 3 4 2 2 【样例输出】 9 【样例说明】 首先给出一种错误的思路： 假设边（1-3）坏了，最短路是1-4-2，距离为3； 假设边（1-4）或（4-2）坏了，最短路是1-3-2，距离为4； 假设边（3-1）或（4-1）或（3-2）坏了，最短路仍为1-4-2，距离为3； 综上，最坏情况下最短路是4。 这种思路的错误在于仍然开启了“上帝视角”。换句话讲，它的决策是基于已知哪条边坏掉的。具体地讲，当我站在1号点时并不能确定边（3-2）和边（4-2）中哪条边坏了，此时我必须决定走（1-3）还是（1-4），而不是根据（3-2）和（4-2）哪条坏了这个信息决定走向3还是走向4。 下面介绍正确思路。首先站在1号点，确认（1-3）有没有坏。如果（1-3）坏了，直接走1-4-2到达终点，距离仅为3。如果（1-3）没坏，先从1走到3。此时站在3，确认（3-2）有没有坏。如果（3-2）坏了，则从3回到1再经过4最终到达2，整个路径为1-3-1-4-2，距离为9；如果（3-2）没坏，则整个路径为1-3-2，距离为4。综上最坏情况下距离为9。 另一种方法是先确认（1-4）有没有坏，如果坏了走1-3-2，如果没坏就走到2再确认（2-4）有没有坏。这种方法最差的可能是1-4-1-3-2，距离为15，不如上一个方法。 【数据规模与约定】 对于20%的数据，n<=5； 对于30%的数据，n<=10； 对于50%的数据，n<=20； 对于100%的数据，n<=100, m<=500, 边的距离不超过1000。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
using namespace std;
struct Edge {
    int y, w, next;
} map[1010];
int num = 0;
int d[110], know[110], head[110], head1[110], flag[110], dis[501][110], dis0[110];
int n, m;
void newedge(int x, int y, int w, int c) {
    map[c].y = y;
    map[c].w = w;
    map[c].next = head[x];
    head[x] = c;
}
void newedge1(int x, int y, int w, int c) {
    map[c].y = y;
    map[c].w = w;
    map[c].next = head1[x];
    head1[x] = c;
}
int main() {
    freopen("blind.in","r",stdin);
    freopen("blind.ans","w",stdout);
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) {
        head[i] = -1;
        head1[i] = -1;
    }
    for (int i=0; i<m; i++) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        newedge(x, y, w, i);
        newedge1(y, x, w, i+m);
    }
    for (int k=0; k<m; k++) {
        int st = 0, ed = 1;
        d[0] = 2;
        for (int i=1; i<=n; i++) flag[i] = true;
        flag[2] = false;
        for (int i=1; i<=n; i++) dis[k][i] = 9999999;
        dis[k][2] = 0;
        while (st < ed) {
            int i = d[(st++) % n];
            for (int j=head1[i]; j>-1; j=map[j].next) {
                if (j == k+m) continue;
                if (dis[k][i] + map[j].w < dis[k][map[j].y]) {
                    dis[k][map[j].y] = dis[k][i] + map[j].w;
                    if (flag[map[j].y]) {
                        flag[map[j].y] = false;
                        d[(ed++) % n] = map[j].y;
                    }
                }
            }
            flag[i] = true;
        }
    }
    for (int i=1; i<=n; i++) {
        know[i] = 0;
        for (int j=head[i]; j>-1; j=map[j].next)
            know[i] = max(know[i], dis[j][i]);
    }
    int st = 0, ed = 1;
    d[0] = 2;
    for (int i=1; i<=n; i++) flag[i] = true;
    flag[2] = false;
    for (int i=1; i<=n; i++) dis0[i] = 9999999;
    dis0[2] = 0;
    while (st < ed) {
        int i = d[(st++) % n];
        for (int j=head1[i]; j>-1; j=map[j].next) {
            if (dis0[map[j].y] > map[j].w + dis0[i] && dis0[map[j].y] > know[map[j].y]) {
                dis0[map[j].y] = max(map[j].w + dis0[i], know[map[j].y]);
                if (flag[map[j].y]) {
                    flag[map[j].y] = false;
                    d[(ed++) % n] = map[j].y;
                }
            }
        }
        flag[i] = true;
    }
    if (dis0[1] == 9999999) dis0[1] = -1;
    printf("%d\n", dis0[1]);
}

打字机(typewriter)

256MB 1seconds 【题目描述】 最近，小J在搬家的过程中发现了一台古老的打字机，好奇的小J决定研究如何使用它。 首先，需要将一条长度为m的纸带放入打字机。打字机上共有26个按键，分别是小写字母’a’-‘z’。每当你按下一个按键时，打字机就会立即在纸带上打印出那个字符，并将纸带平移一个单位距离。 聪明的小J很快就掌握了这款打字机的使用技巧，并尝试一些新的挑战。他拿出了一本字典，挑选了n个单词，并给每个单词设定了分数。纸带中每包含一次指定的单词，就会得到它对应的分数。例如单词’eye’分数为2，’year’分数为3，那么纸带’eyeyeyear’分数为9分。小J希望挑战自己，打出分数最高的纸带。 特别地，小J也会偶尔手抖，按到自己并不想输入的字符。由于这台古老的打字机没有退格（删除）功能，所以小J只能接受按错这个事实，重新规划他在按错的情况下如何得最高分。倘若小J有可能在任意位置按错按键，并保证整个过程中按错的次数不超过k次，那么请你算出他在最坏情况下的最高得分是多少。 【输入格式】 输入数据第一行包含3个非负整数n, m, k，分别表示单词数量、纸带长度和最多按错次数。 随后n行，每行包含一个字符串Si和正整数Ai，由空格隔开，描述这个单词及其得分。 【输出格式】 仅一行，包含一个整数，表示最坏情况下的最大得分。 【输入样例】 2 4 1 w 1 ha 9 【输出样例】 9 【样例说明】 首先，展示一种错误的思路： 共4种情况，即第1位按错、第2位按错、第3位按错和第4位按错。 1、第1位按错（不妨假设按成’x’，下同），最高得分为’xwha’，得分为10。 2、第2位按错，最高得分为’wxha’，同样为10分。 3、第3位按错，最高得分为’haxw’，同样为10分。 4、第4位按错，最高得分为’hawx’，同样为10分。 综上，最坏情况下最高得分为10分。 这种思路的错误之处在于，你不能根据哪一位按错决定你第一位按哪个键。换一种说法，你在哪一位按错，是要在你按下那一个按键之后才能知道的事情。所以正确的思路如下： 1、第1位先按’h’，倘若按对，goto2，倘若按错，goto4， 2、第2位按’a’，倘若按对，goto3，倘若按错，goto5， 3、第3位第4位均按’w’，至多错1次，最终的纸带为’hawx’或’haxw’，得分为10分。 4、由于已经错过1次，后面不会再错，后面三位按’haw’，最终的纸带为’xhaw’，得分为10分。 5、由于已经错过1次，后面不会再错，后面两位按’ha’，最终纸带为’hxha’，得分为9分。 综上，最坏情况下，最高得分为9分。 【数据规模与约定】 对于30%的数据，n=1； 另有30%的数据，k=0； 对于100%的数据，n<=100，m<=500，∑|Si|<=500，Ai<=1000，k<=5。

题解

不愧是标准正解，不需要数据分治，我还是一只蒟蒻啊！！！！ 数据三处分治。。有点怂。。。不过在线提交std却会超时，bzoj上我这道题是rank third！！！ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<cstring>
#include<cstdio>
#define res(i) for(register int i=0;i<=cnt;i++)
#define rez(i) for(register int i=1;i<=26;i++)
#define rep(i,j) for(register int i=0;i<j;i++)
using namespace std; 
char s[510];
long long di[210][210],ret[210][210],tmp[210][210],ans,M,P,tot;
int a[110],ch[510][27],nxt[510],la[510],w[510],cnt,q[510],h,t,x,y,K,m,f[520][520][6],n;
bool used[510][510][6];
void addnew(int v){
    int now=0,n=strlen(s),x;
    rep(i,n){
        x=s[i]-96;
        if(!ch[now][x])ch[now][x]=++cnt;
        now=ch[now][x];
    }
    w[now]+=v;
}
void getnxt(){
    h=1;t=0; 
    rez(i)if(ch[0][i])t++,q[t]=ch[0][i]; 
    while(h<=t){
        x=q[h++]; 
        rez(i){
            int j=ch[x][i]; 
            if(!j){ch[x][i]=ch[nxt[x]][i];continue;} 
            y=nxt[x];
            while(y&&!ch[y][i])y=nxt[y]; 
            nxt[j]=ch[y][i];
            w[j]+=w[nxt[j]]; 
            if(w[nxt[j]])la[j]=nxt[j]; 
            else la[j]=la[nxt[j]]; 
            q[++t]=j;
        }
    }
}
void dp(int n,int x,int k){
    if(k>K||used[n][x][k])return;
    used[n][x][k]=1,f[n][x][k]=w[x];
    if(n==m)return; 
    int maxn=-707185547707185547LL,maxb=0; 
    rez(i){
        dp(n+1,ch[x][i],k); 
        if(k<K)dp(n+1,ch[x][i],k+1); 
        if(f[n+1][ch[x][i]][k]>maxn)maxn=f[n+1][ch[x][i]][k],maxb=i;
    }
    maxn=707185547707185547LL;
    rez(i)if(i==maxb)maxn=min(maxn,f[n+1][ch[x][i]][k]);
          else if(k<K)maxn=min(maxn,f[n+1][ch[x][i]][k+1]);
    f[n][x][k]+=maxn;
}
void slover(int M,bool chu){
    ans=0;if(chu){ 
        memset(di,0xef,sizeof(di)); 
		res(i)rez(j)di[i][ch[i][j]]=w[ch[i][j]]; 
        res(i)res(j)ret[i][j]=di[i][j];M--;
        while(M){
            res(i)res(j)tmp[i][j]=-707185547707185547LL; 
            if(M&1){
                res(i)res(k)res(j)tmp[i][j]=max(ret[i][k]+di[k][j],tmp[i][j]); 
                res(i)res(j)ret[i][j]=tmp[i][j]; 
            } 
            res(i)res(j)tmp[i][j]=-707185547707185547LL; 
            res(i)res(k)res(j)tmp[i][j]=max(tmp[i][j],di[i][k]+di[k][j]); 
            res(i)res(j)di[i][j]=tmp[i][j]; 
            M>>=1;
        } 
        memset(di,0xef,sizeof(di)); 
        res(i)rez(j)di[i][ch[i][j]]=w[ch[i][j]]; 
    }else{ 
        res(i)res(j){ 
            tmp[i][j]=-707185547707185547LL; 
            res(k)tmp[i][j]=max(ret[i][k]+di[k][j],tmp[i][j]); 
        }
        res(i)res(j)ret[i][j]=tmp[i][j]; 
    } 
    res(i)ans=max(ans,ret[0][i]); 
} 
void work(){
    M=m,P=M-300,tot=0;
    for(;P<=M-250;P++){
        rep(i,300)res(j)rep(k,K+1)used[i][j][k]=0; 
        m=M-P;dp(0,0,0); 
        slover(P,(P==M-300)); 
        tot=max(tot,f[0][0][0]+ans); 
    } 
    printf("%lld",tot+1); 
} 
inline int readin(){
	static char ch;int res,flag=1;
	while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
	while((ch=getchar())<='9'&&ch>='0')res=ch-48+res*10;res*=flag;
	return res;
}
int main(){
    //freopen(NAME".in","r",stdin);
	//freopen(NAME".out","w",stdout);
	n=readin(),m=readin(),K=readin();
    rep(i,n)scanf("%s",s),a[i+1]=readin(),addnew(a[i+1]);
    getnxt();
    if(m>500&&K==0&&cnt<=200){slover(m,1);printf("%lld",ans);return 0;}
    if(m>500&&K!=0&&cnt<=51){work();return 0;}
    dp(0,0,0);
    printf("%d",f[0][0][0]);
    return 0;
}

标程 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
const int L = 1010, S=26, M=1010, INF = 99999999;
struct Node {
    Node * son[S];
    Node * next;
    int value;
} node[L];
int n, m, k, x, num=0;
char s[L];
int g1[L], g2[L];
int f1[L][11], f2[L][11];
Node * root;
Node * unknown = node;
Node * new_node() {
    Node * now = &node[num++];
    for (int k=0; k<S; k++)
        now->son[k] = unknown;
    now->next = unknown;
    now->value = 0;
    return now;
}
void init() {
    unknown = new_node();
    root = new_node();
    for (int k=0; k<S; k++)
        unknown->son[k] = root;
}
void build() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i=0; i<n; i++) {
        scanf("%s%d", s, &x);
        int len = strlen(s);
        Node * now = root;
        for (int j=0; j<len; j++) {
            if (now->son[s[j]-'a'] == unknown)
                now->son[s[j]-'a'] = new_node();
            now = now->son[s[j]-'a'];
        }
        now->value += x;
    }
    /*
    for (int i=0; i<num; i++) {
        printf("before: node %d: son = [%d, %d, %d], next = %d, value = %d\n",
                i, node[i].son[0] - node, node[i].son[1] - node, node[i].son[2] - node,
                node[i].next - node, node[i].value);
    }
    */
    queue<Node *> q;
    q.push(root);
    while (!q.empty()) {
        Node * now = q.front();
        q.pop();
        for (int k=0; k<S; k++)
            if (now->son[k] != unknown) {
                now->son[k]->next = now->next->son[k];
                now->son[k]->value += now->next->son[k]->value;
                q.push(now->son[k]);
            } else {
                now->son[k] = now->next->son[k];
            }
    }
    /*
    for (int i=0; i<num; i++) {
        printf("after: node %d: son = [%d, %d, %d], next = %d, value = %d\n",
                i, node[i].son[0] - node, node[i].son[1] - node, node[i].son[2] - node,
                node[i].next - node, node[i].value);
    }
    */
}
void solve_without_k() {
    for (int j=1; j<num; j++) {
        g1[j] = node[j].value;
    }
    for (int i=m-1; i>=0; i--) {
        for (int j=1; j<num; j++) {
            g2[j] = 0;
            for (int c=0; c<S; c++) {
                int t = node[j].son[c] - node;
                g2[j] = max(g2[j], g1[t] + node[j].value);
            }
            //printf("g[%d][%d] = %d\n", i, j, g2[j]);
        }
        for (int j=1; j<num; j++) {
            g1[j] = g2[j];
        }
    }
    printf("%d\n", g2[root-node]);
}
void solve() {
    for (int j=1; j<num; j++) {
            f1[j][0] = node[j].value;
        for (int r=1; r<=k; r++) {
            f1[j][r] = -INF;
            f1[j][r] = node[j].value;
        }
    }
    for (int i=m-1; i>=0; i--) {
        for (int j=1; j<num; j++) {
            for (int r=0; r<=k; r++) {
                f2[j][r] = -INF;
                for (int c=0; c<S; c++) {
                    int t = node[j].son[c] - node;
                    f2[j][r] = max(f2[j][r], f1[t][r] + node[j].value);
                }
                if (r > 0) {
                    for (int c=0; c<S; c++) {
                        int t = node[j].son[c] - node;
                        f2[j][r] = min(f2[j][r], f1[t][r-1] + node[j].value);
                    }
                }
                //printf("g[%d][%d][%d] = %d\n", i, j, r, f2[j][r]);
            }
        }
        for (int j=1; j<num; j++) {
            for (int r=0; r<=k; r++) {
                f1[j][r] = f2[j][r];
            }
        }
    }
    printf("%d\n", f2[root-node][k]);
}
int main () {
	freopen("typewriter.in","r",stdin);
	freopen("typewriter.ans","w",stdout);
    init();
    build();
    //solve_without_k();
    solve();
}

click it and link me

Launch CodeCogs Equation Editor