Reku
0%

Codeforces Div 2 天梯 21——25

Posted on Edited on In Views: Valine:

http://codeforces.com/problemset/problem/269/B 代码写起来还是很好写的，但是想到这个动态规划我确实想了一段时间... \(f_i\) 代表点 \(i\) 不动，前面的所有值都合法的最小移动距离 然后最后设一个肯定不动的点，记录一下最后结果就可以了 

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
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct pp
{
	int s;
	double w;
} p[5010]={};
bool cmp(pp x,pp y)
{
	return x.w<y.w;
}
int f[5010]={};
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i].s;
		cin>>p[i].w;
		f[i]=2147483600;
	}
	sort(p+1,p+n+1,cmp);
	p[n+1].s=m+1;
	f[n+1]=2147483600;
	p[0].s=0;
	for(int i=1;i<=n+1;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(p[j].s<=p[i].s)
			{
				f[i]=min(f[i],f[j]+i-j-1);
			}
		}
	}
	cout<<f[n+1];
	return 0;
}
http://codeforces.com/problemset/problem/478/D 题目倒是很好做...只是我的map一直被卡... 就是一个动态规划... 
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
#include<bits/stdc++.h>
using namespace std;
int mod;
map<int,int> ha[900];
map<int,bool> vis[900];
int r,g,t;
int f;
int ff(int r,int g,int h)
{
	if(h==f) return 1;
	if(vis[h][r]==1) return ha[h][r];
	vis[h][r]=1;
	int u=0;
	if(r>=h)
	{
		u+=ff(r-h,g,h+1);
	}
	if(g>=h)
	{
		u+=ff(r,g-h,h+1);
	}
	u%=mod;
	ha[h][r]=u;
	return u;
}
int main()
{
	mod=1e9+7;
	cin>>r>>g;
	for(f=1;f*(f+1)/2<=r+g;f++);
	cout<<ff(r,g,1);
	return 0;
}
然后不得已只能改成循环的模式... 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
#define maxx 211111
#define mod 1000000007 
using namespace std;
int f[maxx]={1},ans;
int main()
{
	int i,j,n,m,h;
	cin>>n>>m;
	for(h=1;h*(h+1)/2<=n+m;h++); h--;
	for(i=1;i<=h;i++)
		for(j=n;j>=i;j--)
			f[j]=(f[j]+f[j-i])%mod;
	for(j=max(0,h*(h+1)/2-m);j<=n;j++) ans=(ans+f[j])%mod;	
	cout<<ans;
}
上下两个程序的时间复杂度基本没什么变化...但是相差的常数确实有些难以接受... http://codeforces.com/problemset/problem/375/B 最开始的时候看错题了...写了一个悬线法极大子矩阵... 
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
#include<bits/stdc++.h>
using namespace std;
int h[5010][5010]={};
int l[5010][5010]={};
int r[5010][5010]={};
int ll[5010][5010]={};
int rr[5010][5010]={};
bool e[5010][5010]={};
int n,m;
char c;
int p;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c;
			if(c=='0') e[i][j]=0;
			else e[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		p=0;
		for(int j=1;j<=m;j++)
		{
			if(e[i][j]==0) p=j;
			ll[i][j]=p+1; 
		}
	}
	for(int i=1;i<=n;i++)
	{
		p=m+1;
		for(int j=m;j>=1;j--)
		{
			if(e[i][j]==0) p=j;
			rr[i][j]=p-1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(e[i][j]==1)
			{
				if(e[i-1][j]==0)
				{
					h[i][j]=1;
					l[i][j]=ll[i][j];
					r[i][j]=rr[i][j];
				}
				else
				{
					h[i][j]=h[i-1][j]+1;
					l[i][j]=max(ll[i][j],l[i-1][j]);
					r[i][j]=min(rr[i][j],r[i-1][j]);
				}
				//cout<<i<<" "<<j<<" "<<h[i][j]<<" "<<l[i][j]<<" "<<r[i][j]<<endl;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]);
		}
	}
	printf("%d",ans);
	return 0;
}
后来明确了题意之后，感觉是一个动态规划的问题... \(f_{ij}\) 代表从i开始到j结束，这一段被覆盖了多少次... 然后可以在 \(O(N*M)\) 的复杂度构建这个数组... 然后就可以求一下 \(f\) 的后缀和，算一算就可以了 然后通过这个题，我发现scanf比getchar慢了好多啊... 
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
#include<iostream>
using namespace std;
int n,m;
int e[5010][5010]={};
int f[5010][5010]={};
int h[5010][5010]={};
int q[5010]={};
char c;
int l,r;
int main()
{
	scanf("%d%d",&n,&m);
	scanf("%c",&c);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			c=getchar();
			if(c=='0') e[i][j]=0;
			else e[i][j]=1;
		}
		if(i!=n) scanf("%c",&c);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(e[i][j]==1)
			{
				if(e[i][j-1]==0) l=j;
				r=j;
				if(e[i][j+1]==0)
				{
					for(int k=l;k<=r;k++)
					{
						f[k][r]++;
						q[k]=max(q[k],r);
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=q[i];j>=i;j--)
		{
			h[i][j]=h[i][j+1];
			h[i][j]+=f[i][j];
			ans=max(h[i][j]*(j-i+1),ans);
		}
	}
	printf("%d",ans);
	return 0;
}

http://codeforces.com/problemset/problem/283/B 在这道题中再一次见识到了memset的缓慢... 说实话，题目还是很简单的...动态规划 \(e_{i2}\) 和\(e_{i3}\) 代表从 \(x\) 走到1或者结束游戏时候的 \(x\) 值 \(p_{i2}\) 和\(p_{i3}\) 代表从 \(x\) 走到1或者结束游戏时候的 \(y\) 的变化值 \(t_{i2}\) 和\(t_{i3}\) 代表从 \(x\) 走到1或者结束游戏时候的进行的步骤... 然后1的情况其实只有两种，每一个 \(i\) 单独算一算就行了... 实现比较复杂吧...其实也还好，一遍就写对了，主要卡在了每次的memset...改一改就好了... 

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
#include<bits/stdc++.h>
using namespace std;
bool v[200010][4]={};
bool w[200010][4]={};
long long e[200010][4]={};
long long p[200010][4]={};
short t[200010][4]={};
long long a[200010]={};
long long n;
struct pp
{
	long long e,p,t;
} u;
pp ff(long long x,short d)
{
	pp o;
	if(x<=1||x>n)
	{
		o.e=x;
		o.p=0;
		o.t=d;
		return o;
	}
	if(w[x][d]==1)
	{
		o.e=-2147483644;
		w[x][d]=0;
		return o;
	}
	if(v[x][d]==1)
	{
		o.e=e[x][d];
		o.p=p[x][d];
		o.t=t[x][d];
		return o;
	}
	v[x][d]=1;
	w[x][d]=1;
	if(d==2)
	{
		o=ff(x-a[x],3);
		e[x][d]=o.e;
		p[x][d]=o.p+a[x];
		t[x][d]=o.t;
	}
	else
	{
		o=ff(x+a[x],2);
		e[x][d]=o.e;
		p[x][d]=o.p+a[x];
		t[x][d]=o.t;
	}
	o.e=e[x][d];
	o.p=p[x][d];
	o.t=t[x][d];
	w[x][d]=0;
	return o;
}
int main()
{
	scanf("%I64d",&n);
	for(int i=2;i<=n;i++)
	{
		scanf("%I64d",&a[i]);
	}
	for(int i=2;i<=n;i++)
	{
		if(v[i][2]==0)
		{
			u=ff(i,2);
			e[i][2]=u.e;
			p[i][2]=u.p;
			t[i][2]=u.t;
		}
		if(v[i][3]==0)
		{
			u=ff(i,3);
			e[i][3]=u.e;
			p[i][3]=u.p;
			t[i][3]=u.t;
		}
	}
	long long ans;
	long long r;
	int h;
	for(int i=1;i<n;i++)
	{
		a[1]=i;
		r=e[1+a[1]][2];
		if(r==-2147483644)
		{
			printf("-1\n");
			continue;
		}
		else if(r<=0||r>n)
		{
			printf("%I64d\n",p[1+a[1]][2]+a[1]);
			continue;
		}
		else
		{
			h=t[1+a[1]][2];
			if(h==3)
			{
				printf("-1\n");
				continue;
			}
			else
			{
				printf("%I64d\n",p[1+a[1]][2]+a[1]+a[1]);
				continue;
			}
		}
	}
	return 0;
}
http://codeforces.com/contest/329/problem/B 看了半天...我也没看懂题目... 然后就复制了一下... 似乎就是一个条件很多的广搜？... 
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
#include <bits/stdc++.h>
using namespace std;

int mp[1009][1009],a[1009][1009];
queue <int> vx;
queue <int> vy;
int r,c;

void bfs(int x,int y,int t)
{
	if (x<0 || x==r || y<0 || y==c || a[x][y]) return;
	if (mp[x][y]==-1) return;
	a[x][y]=t;
	vx.push(x+1),vy.push(y);
	vx.push(x),vy.push(y+1);
	vx.push(x-1),vy.push(y);
	vx.push(x),vy.push(y-1);
}

int main()
{
	cin >> r >> c;
	int xx,yy;
	for (int i=0;i<r;i++)
		for (int j=0;j<c;j++)
		{
			char c;
			cin >> c;
			if (c=='E') vx.push(i),vy.push(j);
			else if (c=='S') xx=i,yy=j;
			else if (c=='T') mp[i][j]=-1;
			else mp[i][j]=c-'0';
		}
	int l=1;
	while (vx.size())
	{
		int s=vx.size();
		for (int i=0;i<s;i++)
		{
			bfs(vx.front(),vy.front(),l);
			vx.pop();
			vy.pop();
		}
		l++;
	}
	int count=0;
	for (int i=0;i<r;i++)
		for (int j=0;j<c;j++)
			if (a[i][j]<=a[xx][yy] && a[i][j]!=0 && mp[i][j]>0) count+=mp[i][j];
	cout << count << endl;
}