《算法竞赛入门经典训练指南》动态规划习题1

动态规划习题(1)

入门习题 (Exercises: Beginner)

UVa11584Partitioning by Palindromes入门题目
LA4256Salesman入门题目
UVa10534Wavio Sequence可以转化为经典问题，时间O(nlogn)
UVa11552Fewest Flops序列划分模型；状态设计
UVa11404Palindromic Subsequence可以转化为LCS
LA4731Cellular Network需要一点概率知识和推理
UVa11795Mega Man's Missions基础的集合动态规划
LA4727JumpJoseph问题的变形
LA3530Martian Mining模型简单，但需要减少重复计算
UVa10564Paths through the Hourglass类似01 背包问题
UVa10817Headmaster's Headache集合动态规划
LA2038Strategic Game树上动态规划（基础题）
LA3363String Compression字符串动态规划
LA2031Dance Dance Revolution以跳舞机为背景的题目
LA4643Twenty Questions有趣的问题；比较基础的动态规划
(extra)UVa10163Storage Keepers
(extra)UVa10453Make Palindrome
(extra)UVa10254The Priest Mathematician
(extra)UVa437The Tower of Babylon
(extra)UVa442Matrix Chain Multiplication最优矩阵乘法
(extra)UVa473Raucous Rockers可以优化
(extra)UVa590Always on the Run
(extra)UVa607Scheduling Lectures
(extra)UVa662Fast Food可以优化
(extra)UVa672Gangsters

中级习题 (Exercises：Intermediate)

LA4945Free Goodies也可以贪心，时间效率更高
LA4327Parade模型不难想，但需要优化
LA4015Cave树的动态规划
LA4490Help Bubu
UVa11600Masud Rana注意状态表示
LA4987Evacuation Plan
LA4613Mountain Road
LA4614Moving to Nuremberg
LA4050Hanoi Towers
LA3305Tour经典问题
LA3412Pesky Heroes树的动态规划（题目不太好理解）
LA3679Pitcher Rotation需要一点优化（精简状态）
LA3605Roommate
LA3608Period
LA3610Log Jumping可以转化为经典问题
LA2221Frontier涉及到几何（见第四章）的动态规划
LA3132Minimax Triangulation
LA3710Interconnect注意状态表示
LA5088Alice and Bob's Trip树上的动态规划
LA3782Bigger is Better有多种方法。可以不用高精度
(extra)UVa10003Cutting Sticks经典的动态规划题目。可以用四边形不等式优化
(extra)UVa10239The Book-shelver's Problem
(extra)UVa10271Chopsticks
(extra)UVa10304Optimal Binary Search Tree
(extra)UVa10599Robots(II)
(extra)UVa10604Chemical Reaction
(extra)UVa10618Tango Tango Insurrection
(extra)UVa10641Barisal Stadium
(extra)UVa10671Grid Speed
(extra)UVa10688The Poor Giant
(extra)UVa11263Nested Rectangles
(extra)UVa11400Lighting System Design
(extra)UVa11578Situp Benches
(extra)UVa11691Allergy Test
(extra)UVa11766Racing Car Computer
(extra)UVa12002Happy Birthday
(extra)UVa10723Cyborg Genes推荐
(extra)UVa10934Dropping water推荐
(extra)UVa10981String Morphing推荐
(extra)UVa11307Alternative Arborescene推荐
(extra)UVa11456Trainsorting
(extra)UVa11782Optimal Cut
(extra)LA2096Taekwondo
(extra)LA2151Telescope

提高习题 (Exercises: Advanced)

LA4394String Painter序列的动态规划，有一定难度
LA4593Exclusive Access 2
LA4048Fund Management注意状态表示
LA4625Garlands
LA3683A Scheduling Problem树的动态规划
LA3637The Bookcase不太容易想到，且需要优化
LA5717Peach Blossom Spring一类经典题目（最早出现在NWERC2006，但本题数据更强）
LA3623The Best Name for Your Baby有难度的动态规划；注意计算顺序
LA4002The Ultimate Password有难度的动态规划；注意计算顺序
LA2178The Minimum Number of Rooks有难度的动态规划
LA2923Bundling
LA2930Minimizing Maximizer01 原则；数据结构优化动态规划
LA3181Fixing the Great Wall
LA4290Easy Climb需要优化
UVa10559Blocks重点是设计状态及其转移
LA4031Integer Transmission需要认真思考。可以做到O(n^2)时间。
UVa11521Compressor需要认真思考。很容易写错。
(extra)UVa10949Kids in a Grid
(extra)UVa11193Infinix
(extra)UVa11194Stone Grid
(extra)UVa11810Gentle ping, to the old King
(extra)UVa11171SMS
(extra)UVa11435Network EXTREME!!!推荐
(extra)UVa11502Rocket Stages
(extra)UVa11750Red-Blue Tree推荐
(extra)UVa11803The Great Merge

展开全文 >>

《算法竞赛入门经典训练指南》动态规划习题2

动态规划习题(2)

划分成回文串（Partitioning by Palindromes, Uva 11584）

简单动态规划，用dp[i]表示前i部分的划分情况。记录每个点j，以j为中点的回文串长度，然后dp[i]=min(dp[i-s-1]|其中a[i-s~i]为回文串)

Uva 11584 Partitioning by Palindromesview raw
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
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define setmax(a) memset(a,0x7f,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

const int maxn=1005;
char s[maxn];
int dp[maxn];
int hw[maxn];
int hw2[maxn];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",s+1);
		int l=strlen(s+1);
		int i,j;
		for(i=1;i<=l;i++)
		{
			hw[i]=hw2[i]=0;
			for(j=0;i+j<=l&&i-j>0;j++)
			{
				if(s[i+j]==s[i-j])
					hw[i]++;
				else
					break;
			}
			for(j=0;i+j+1<=l&&i-j>0;j++)
			{
				if(s[i+j+1]==s[i-j])
					hw2[i]++;
				else
					break;
			}
		}
		zero(dp);
		for(i=1;i<=l;i++)
		{
			dp[i]=dp[i-1]+1;
			for(j=1;j<i;j++)
			{
				if(hw[j]+j-1>=i)
					dp[i]=min(dp[i],dp[2*j-i-1]+1);
				if(hw2[j]+j>=i)
					dp[i]=min(dp[i],dp[2*j-i]+1);
			}
		}
		printf("%d\n",dp[l]);
	}
    return 0;
}
more >>

展开全文 >>

《算法竞赛入门经典训练指南》高效算法设计举例1

高效算法设计举例(1)

例题17 年龄排序（Age Sort，Uva11462）

计数排序

Uva 11462 Age Sortview raw
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
#include<cstdio>
#include<cstring>
int a[105];
int main()
{
	int n;
	while(scanf("%d",&n),n)
	{
		int k;
		memset(a,0,sizeof(a));
		while(n--)
		{
			scanf("%d",&k);
			a[k]++;
		}
		bool sc=0;
		for(int i=1;i<=100;i++)
		{

			while(a[i]--)
			{
				if(sc)
					printf(" ");
				sc=1;
				printf("%d",i);
			}
		}
		printf("\n");
	}
}
more >>

展开全文 >>

《算法竞赛入门经典训练指南》高效算法设计举例2

高效算法设计举例(2)

例题21 子序列（Subsequence, SEERC 2006, LA 2678）

简单题

LA 2678 - Subsequenceview raw
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
#include<cstdio>
#include<iostream>
using namespace std;
int a[100005];
const int inf=200000;
int main()
{
	int n,s;
	while(~scanf("%d%d",&n,&s))
	{
		int i,j;
		int sum=0;
		int len=inf;
		int k=-1;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
			while(sum>=s)
			{
				len=min(len,i-k);
				sum-=a[++k];
			}
			if(sum<0)
			{
				len=1;
				k=i;
				sum=0;
			}
		}
		if(len==inf)
			printf("0\n");
		else
			printf("%d\n",len);
	}
}
more >>

展开全文 >>

《算法竞赛入门经典训练指南》问题求解常见策略1

问题求解常见策略(1)

例题7 偶数矩阵（Even Parity，Uva11464）

枚举题，只需要枚举处第一行的最终状态就可以推出其他行，然后在判断是否满足变换规则。最后找出最小变动量

Uva11464view raw
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
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))
#define MAX 10000000
struct{
	int x,y;
}a[20][20];
int n;

int check(int k)
{
	int i;
	for(i=0;i<n;i++)
		a[0][i].y=0;
	i=0;
	while(k)
	{
		a[0][i].y=k%2;
		k=k/2;
		i++;
	}

	for(i=0;i<n;i++)
		if(a[0][i].x==1&&a[0][i].y==0)
			return -1;

	return 0;			
}
int fun()
{
	int i,j;
	for(i=1;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			int sum=0;
			if(i>=2)
				sum+=a[i-2][j].y;
			if(j>0)
				sum+=a[i-1][j-1].y;
			if(j<n-1)
				sum+=a[i-1][j+1].y;
			if(sum%2==0)
				a[i][j].y=0;
			else
				a[i][j].y=1;
			if(a[i][j].y==0&&a[i][j].x==1)
				return MAX;
		}

	}

	int cnt=0;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(a[i][j].x==0&&a[i][j].y==1)
				cnt++;

	return cnt;
}
int main()
{
	int T;
	int cas=1;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		int i,j;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				scanf("%d",&a[i][j].x);
			}
		}

		int ans=MAX;

		for(i=0;i<(1<<n);i++)
		{
			if(check(i)==-1)
				continue;
			ans=min(ans,fun());
		}
		if(ans!=MAX)
			printf("Case %d: %d\n",cas++,ans);
		else
			printf("Case %d: -1\n",cas++);
	}
     return 0;
}
more >>

展开全文 >>

《算法竞赛入门经典训练指南》问题求解常见策略2

问题求解常见策略(2)

例题12 组装电脑（Assemble，LA3971，POJ3497）

简单二分

POJ 3497 - Assembleview raw
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
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

struct prog{
	char type[25];
	char name[25];
	int price;
	int quality;
}com[1010];
bool compare_type(prog a,prog b)
{
	if(strcmp(a.type,b.type)==0)
	{
		if(a.quality==b.quality)
			return a.price<b.price;
		return a.quality<b.quality;
	}
	if(strcmp(a.type,b.type)>0)
		return 1;
	return 0;
}
int com_start[1010];
int com_type;
int n,b;
int erfen(int s,int t)
{
	if(s==t)
		return s;
	int m=(s+t)/2+1;
	int i,j;
	int sum=0;
	for(i=0;i<com_type;i++)
	{
		int less=1000000;
		for(j=com_start[i];j<com_start[i+1];j++)
		{
			if(com[j].quality>=m)
			{
				less=min(less,com[j].price);
			}
		}
		sum+=less;
	}
	if(sum<=b)
		return erfen(m,t);
	else
		return erfen(s,m-1);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int i,j,k;
		scanf("%d%d",&n,&b);
		int max_quality,min_quality;
		max_quality=0;
		min_quality=1000000000;
		for(i=0;i<n;i++)
		{
			scanf("%s%s%d%d",&com[i].type,&com[i].name,&com[i].price,&com[i].quality);
			max_quality=max(max_quality,com[i].quality);
			min_quality=min(min_quality,com[i].quality);
		}
		sort(com,com+n,compare_type);

		com_start[0]=0;
		for(j=1,i=1;i<n;i++)
		{
			if(strcmp(com[i].type,com[i-1].type))
				com_start[j++]=i;
		}
		com_type=j;
		com_start[j]=n;
		printf("%d\n",erfen(min_quality,max_quality));
	}
    return 0;
}
more >>

展开全文 >>

《算法竞赛入门经典训练指南》动态规划专题1

动态规划专题(1)

例题26 约瑟夫环的变形（And Then There Was One, Japan 2007, LA 3882, POJ 3517）

经典问题，递推解决

poj 3517view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
int main()
{
	int n,m,k;
	while(scanf("%d%d%d",&n,&k,&m),n||m||k)
	{
		int i;
		int ans=0;
		for(i=2;i<=n;i++)
			ans=(ans+k)%i;
		ans=(ans+m-k+1)%n;
		while(ans<=0)
			ans+=n;
		printf("%d\n",ans);
	}
}

例题27 王子和公主（Prince and Princess, Uva 10635）

LCS问题，可转为LIS问题

Uva 10635view raw
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
#include <cstdio>
#define zero(a) memset(a,0,sizeof(a))
int dp[630000],mp[630000];
void erfen(int l,int r,int k)
{
	while(l<r)
	{
		int m=(l+r)/2;
		if(dp[m]<k) l=m+1;
		else r=m;
	}
	dp[l]=k;
}
int main()
{
	int T,cas=1;
	scanf("%d",&T);
	while(T--)
	{
		int n,p,q,i,j,k;
		scanf("%d%d%d",&n,&p,&q);
		zero(mp);
		for(i=0;i<=p;i++)
		{
			scanf("%d",&k);
			mp[k]=i+1;
		}
		zero(dp);
		j=0;
		for(i=1;i<=q+1;i++)
		{
			scanf("%d",&k);
			k=mp[k];
			if(k>dp[j])
			{
				dp[j+1]=k;
				j++;
			}
			else if(k!=0)
			{
				erfen(0,j,k);
			}
		}
		printf("Case %d: %d\n",cas++,j);
	}
    return 0;
}
more >>

展开全文 >>

《算法竞赛入门经典训练指南》动态规划专题2

动态规划专题(2)

例题30 放置街灯（Placing Lampposts, Uva 10859）

动态规划，比较复杂的一题。通过这题，学到一个技巧

一般来说，如果题目要求两个量v1,v2，若要求满足v1最大或最小的时候，v2同事也要最大或最小。则可以把v1和v2合成一个量x=M*v1+v2.其中M要是比v2的理论值与v1理论值之差还要大的数,最后就求出v1=x/M，v2=x%M。因为要v1和v2同增或同减，则对于此题，M可取2000，v1为点灯数，v2为只被一盏灯照到的边的数。

解决此题，首先将无根树转换成有根树，用dp[i][j]来表示对于节点i父节点点灯状态为j时的最小x值，注意当i为根的时候的特殊情况，详细看代码

Uva 10859view raw
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
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

vector<int>d[1005];
bool vis[1005][2];
int dp[1005][2];
const int bs=2000;
int DFS(int i,int j,int f)
{
	if(vis[i][j]==1)
		return dp[i][j];
	vis[i][j]=1;
	int k;
	int ans1,ans2;
	ans1=bs;
	for(k=0;k<d[i].size();k++)
	{
		if(d[i][k]!=f)
		{
			ans1+=DFS(d[i][k],1,i);
		}
	}
	if(f>=0&&(!j))
		ans1++;
	dp[i][j]=ans1;
	ans2=0;
	if(j||f<0)
	{
		for(k=0;k<d[i].size();k++)
		{
			if(d[i][k]!=f)
			{
				ans2+=DFS(d[i][k],0,i);
			}
		}
		if(f>=0)
			ans2++;
		dp[i][j]=min(ans1,ans2);
	}
	return dp[i][j];
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		int i;
		for(i=0;i<1005;i++)
			d[i].clear();
		for(i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			d[a].push_back(b);
			d[b].push_back(a);
		}
		zero(vis);
		zero(dp);
		int ans=0;
		for(i=0;i<n;i++)
		{
			if(!vis[i][0])
				ans+=DFS(i,0,-1);
		}
		printf("%d %d %d\n",ans/bs,m-ans%bs,ans%bs);
	}
    return 0;
}
more >>

展开全文 >>

《算法竞赛入门经典训练指南》思维的体操

思维的体操

例题1 勇者斗恶龙（The Dragon of Loowater，Uva 11292）

贪心水题

Uva 11292view raw
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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int d[20005],x[20005];
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m),n||m)
	{
		int i,j,k;
		for(i=0;i<n;i++)
			scanf("%d",&d[i]);
		for(i=0;i<m;i++)
			scanf("%d",&x[i]);

		sort(d,d+n);
		sort(x,x+m);

		j=0;
		int sum=0;
		for(i=0;i<n;i++)
		{
			while(j<m&&x[j]<d[i])
				j++;
			if(j==m)
				break;
			if(j!=m)
				sum+=x[j++];
		}

		if(i!=n)
			printf("Loowater is doomed!\n");
		else
			printf("%d\n",sum);
	}
	return 0;
}
more >>

展开全文 >>

20111120周赛解题报告

Problem A: 不服气的数字

假设可以去的2数有k个

如果要求取得没有0,则答案为:$k^1+k^2+k^3+……+k^n$

如果要求取得数含有0,则答案为:$k+{(k-1)}k+(k-1)k^2+(k-1)k^3+…(k-1)k^{(n-1)}=k^n$（也可以看成k进制，直接得出答案）

不服气的数字参考代码view raw
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
#include <iostream>
#include<cstring>
#include<cstdio>
using namespace std;
bool hash[10];
long long ans[1000005];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        memset(hash,0,sizeof(hash));
        while(m--)
        {
            int a;
            cin>>a;
            hash[a]=1;
        }
        m=0;
        int i;
        for(i=0;i<10;i++)
            if(hash[i]==0)
                m++;
        ans[0]=1;
        for(i=1;i<=n;i++)
            ans[i]=ans[i-1]*m%1000000007;
        if(hash[0])
        {
            long long sum=0;
            for(i=1;i<=n;i++)
                sum=(sum+ans[i])%1000000007;
            cout<<sum<<endl;
        }
        else
        {
            cout<<ans[n]<<endl;
        }
    }
    return 0;
}

 

more >>

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

小龙少，年二十有二。始从文，连考而不中。遂习武，练武场上发一矢，中鼓吏，逐之出。改学IT，自建一变量，用之，烫烫烫烫烫烫烫烫烫烫！