POJ 2704(Pascal's Travels-裸dp)

Posted on 25 3 月, 2013 by nike0good

Language:

Pascal's Travels

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4821		Accepted: 2139

Description

An n x n game board is populated with integers, one nonnegative integer per square. The goal is to travel along any legitimate path from the upper left corner to the lower right corner of the board. The integer in any one square dictates how large a step away
from that location must be. If the step size would advance travel off the game board, then a step in that particular direction is forbidden. All steps must be either to the right or toward the bottom. Note that a 0 is a dead end which prevents any further
progress.

Consider the 4 x 4 board shown in Figure 1, where the solid circle identifies the start position and the dashed circle identifies the target. Figure 2 shows the three paths from the start to the target, with the irrelevant numbers in each removed.

Input

The input contains data for one to thirty boards, followed by a final line containing only the integer -1. The data for a board starts with a line containing a single positive integer n, 4 <= n <= 34, which is the number of rows in this board. This is followed
by n rows of data. Each row contains n single digits, 0-9, with no spaces between them.

Output

The output consists of one line for each board, containing a single integer, which is the number of paths from the upper left corner to the lower right corner. There will be fewer than 2⁶³ paths for any board.

Sample Input

Sample Output

3
0
7

Hint

Brute force methods examining every path will likely exceed the allotted time limit. 64-bit integer values are available as long values in Java or long long values using the contest's C/C++ compilers.

Source

Mid-Central USA 2005

就是dp……

一开始忘打‘n’ wa了……

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN (34+1)
int a[MAXN][MAXN],n;
long long f[MAXN][MAXN];
int main()
{
	while (scanf("%d",&n)&&n+1)
	{
		for (int i=1;i<=n;i++)
		{
			char s[MAXN];
			scanf("%s",s+1);
			for (int j=1;j<=n;j++) a[i][j]=s[j]-'0';
		}
		memset(f,0,sizeof(f));f[1][1]=1;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				if (a[i][j])
				{
					if (i+a[i][j]<=n) f[i+a[i][j]][j]+=f[i][j];
					if (j+a[i][j]<=n) f[i][j+a[i][j]]+=f[i][j];
				}
		printf("%lldn",f[n][n]);
	}
	return 0;
}

CH 白色情人节1(②第一天-KM算法)

Posted on 25 3 月, 2013 by nike0good

背景

下过雨的夏天傍晚我都会期待
唱歌的蝉嘿把星星都吵醒月光晒了很凉快
就是这样回忆起来第一次告白
尴尬的我看爱装得很哲学的你其实很可爱
你说活在明天活在期待不如活得今天很自在
我说我懂了会不会太快未来第一天要展开

描述

时间回溯到男女主认识的第一天——女主同学举办的联谊会，男主迟到了那天的联谊会，而男主到达现场时女主也刚好没有男伴，这就是他们的第一次相遇。

男主回想起来不禁一阵感慨(为啥这么好的妹子你们都不搭讪呢)，突然男主想到，如果当时已经配对的n对男女好感值之和不是最大，会不会自己就遇不上女主了呢？

输入格式

第一行两个正整数n和queen，表示已有n对男女可以配对和女主的编号queen。(男编号为X₁~X_n，女编号为Y₁~Y_n+1)

接下来n*(n+1)行，每行三个正整数X_i，Y_i，Z_i，表示男X_i女Y_i之间的好感度为Z_i，保证每对(X_i,Y_i)没有重复，即两人的关系至多一条。

不存在男与男、女与女之间的好感度！

输出格式

前n行输出联谊会上n对男女的配对情况(会多出来一名女生)，每行两个正整数X_i和Y_i(空格隔开)，任意一种符合条件的方案均可。

第n+1行，对于你输出的方案，如果女主未配对，输出"YES"(不含引号)，表示女主会遇到男主，否则输出"NO"(不含引号)。

样例输入

样例输出

1 2
2 1
YES

数据范围与约定

对于100%的数据， $1leq nleq 520,1leq Z_{i}leq 201314$ 。

样例解释

如图，已经配对的关系有是男1号女2号和男2号女1号。

来源

*****关系~

km算法

就是二分图匹配时维护lx[i],ly[i]

满足

1.对于任意边lx[i]+ly[i]>=w[i,j]

2.如果存在一组匹配，其中任意边满足lx[i]+ly[i]=w[i,j]，它一定是最大匹配（如果随意调换一边，必然出现lx[i]+ly[j]+lx[i']+ly[j']=w[i,j]+w[i',j']≥w[i,j']+w[i',j]

于是每次找出slock，表示对所有找过的i,不为0的min(lx[i]+ly[j]-w[i,j])

把slock的值从左移至右，既不改变原图能走的边，又能使图得到扩充。

//一开始应该把lx[i]设成max(w[i,j],0),ly[i]设成0

每次扩充必须保证图中的边满足lx[i]+ly[i]=w[i,j]，否则用slock扩充

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
using namespace std;
#define INF (100000000)
#define MAXN (520+10)
#define MAXWi (201314)
int n,m,yi,slack;
int w[MAXN][MAXN],lx[MAXN],ly[MAXN],a[MAXN];//a=?->yi
bool vx[MAXN],vy[MAXN];
bool find(int x)
{
	vx[x]=1;
	for (int i=1;i<=m;i++)
		if (!vy[i])
		{
			int t=lx[x]+ly[i]-w[x][i];
			if (t==0)
			{
				vy[i]=1;
				if (a[i]==0||find(a[i])) {a[i]=x;return 1;}
			}else slack=min(slack,t);
		}
	return 0;
}
int main()
{
//	freopen("input","r",stdin);
	scanf("%d%d",&n,&yi);m=n+1;
	memset(lx,0,sizeof(lx));
	memset(ly,0,sizeof(ly));
	memset(a,0,sizeof(a));
	for (int i=1;i<=n*(n+1);i++)
	{
		int u,v,wei;scanf("%d%d%d",&u,&v,&wei);w[u][v]=wei;
		lx[u]=max(lx[u],wei);
	}
	for (int i=1;i<=n;i++)
	{
		memset(vx,0,sizeof vx);
		memset(vy,0,sizeof vy);
		slack=INF;
		while (!find(i))
		{
			for (int j=1;j<=n;j++) if (vx[j]) lx[j]-=slack;
			for (int j=1;j<=m;j++) if (vy[j]) ly[j]+=slack;
			memset(vx,0,sizeof vx);
			memset(vy,0,sizeof vy);
			slack=INF;
		//	find(i);
		}
	}
	for (int i=1;i<=m;i++)
	{
		if (a[i]) printf("%d %dn",a[i],i);
	}
	if (a[yi]) printf("NOn");
	else printf("YESn");
	return 0;
}

CF 286C(Main Sequence-贪心括号匹配)

Posted on 25 3 月, 2013 by nike0good

As you know, Vova has recently become a new shaman in the city of Ultima Thule. So, he has received the shaman knowledge about the correct bracket sequences. The shamans of Ultima Thule have been using lots of different types of brackets since prehistoric times.
A bracket type is a positive integer. The shamans define a correct bracket sequence as follows:

An empty sequence is a correct bracket sequence.
If {a₁, a₂, ..., a_l} and {b₁, b₂, ..., b_k} are
correct bracket sequences, then sequence {a₁, a₂, ..., a_l, b₁, b₂, ..., b_k} (their
concatenation) also is a correct bracket sequence.
If {a₁, a₂, ..., a_l} —
is a correct bracket sequence, then sequence also is a correct bracket sequence, where v (v > 0) is
an integer.

For example, sequences {1, 1, - 1, 2, - 2, - 1} and {3, - 3} are
correct bracket sequences, and {2, - 3} is not.

Moreover, after Vova became a shaman, he learned the most important correct bracket sequence {x₁, x₂, ..., x_n},
consisting of nintegers. As sequence x is the most
important, Vova decided to encrypt it just in case.

Encrypting consists of two sequences. The first sequence {p₁, p₂, ..., p_n} contains
types of brackets, that is, p_i = |x_i| (1 ≤ i ≤ n).
The second sequence {q₁, q₂, ..., q_t} contains t integers
— 这些地方必须取负数 {x₁, x₂, ..., x_n}.

Unfortunately, Vova forgot the main sequence. But he was lucky enough to keep the encryption: sequences {p₁, p₂, ..., p_n} and{q₁, q₂, ..., q_t}.
Help Vova restore sequence x by the encryption. If there are multiple sequences that correspond to the encryption, restore any of them. If there are no
such sequences, you should tell so.

Input

The first line of the input contains integer n (1 ≤ n ≤ 10⁶).
The second line contains n integers: p₁, p₂, ..., p_n (1 ≤ p_i ≤ 10⁹).

The third line contains integer t (0 ≤ t ≤ n),
followed by t distinct integers q₁, q₂, ..., q_t (1 ≤ q_i ≤ n).

The numbers in each line are separated by spaces.

Output

Print a single string "NO" (without the quotes) if Vova is mistaken and a suitable sequence {x₁, x₂, ..., x_n} doesn't
exist.

Otherwise, in the first line print "YES" (without the quotes) and in the second line print n integers x₁, x₂, ..., x_n (|x_i| = p_i; x_q_j < 0).
If there are multiple sequences that correspond to the encrypting, you are allowed to print any of them.

Sample test(s)

input
2
1 1
0

output
YES
1 -1

input
4
1 1 1 1
1 3

output
YES
1 1 -1 -1

input
3
1 1 1
0

output
NO

input
4
1 2 2 1
2 3 4

output
YES
1 2 -2 -1

贪心，从后向前做，尽可能取左括号。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
using namespace std;
#define MAXN (1000000+10)
#define MAXP (1000000000+10)
int n,m,a[MAXN],ans[MAXN],tot;
bool b[MAXN];
int s[MAXN],size=0;
int main()
{
	memset(b,0,sizeof(b));
	scanf("%d",&n);tot=n+1;
	if (n%2) {printf("NOn");return 0;}
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		int p;
		scanf("%d",&p);
		b[p]=1;
	}
	for (int i=n;i;i--)
	{
		if (size==0||s[size]!=a[i]||b[i])
		{
			s[++size]=a[i];ans[--tot]=-a[i];
		}
		else ans[--tot]=s[size--];
	}
	if (size) printf("NOn");
	else
	{
		printf("YESn");
		for (int i=1;i<n;i++) printf("%d ",ans[i]);printf("%dn",ans[n]);
	}

	return 0;
}

圈地(斜率排序+坐标系旋转)

Posted on 25 3 月, 2013 by nike0good

Problem 2 圈地(land.cpp/c/pas)

【题目描述】

2维平面上有n个木桩，你有一次圈地的机会并得到圈到的土地，为了体现你的高风亮节，你要使你圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形，多边形的顶点就是一个木桩，圈得的土地就是这个多边形内部的土地。

【输入格式】

第一行一个整数n，表示木桩个数。
　　接下来n行，每行2个整数表示一个木桩的坐标，坐标两两不同。

【输出格式】

仅一行，表示最小圈得的土地面积，保留2位小数。

【样例输入】

样例1：
3

0 0

0 1

1 0

样例2：
4

0 0

0 1

0 2

1 1

【样例输出】

样例1：
0.50
样例2：
0.00
【数据范围】

对于10%的数据，n<=100；
　对于30%的数据，n<=300；
　对于50%的数据，n<=500；
　对于100%的数据，n<=1000。

显然这题的多边形一定是三角形。

首先求出所有边，按k排序（必须先求出来，不能直接在排序的时候求）

然后考虑这些边，会发现正好是绕坐标系旋转一圈。

也就是说如果按照以这边为y轴从左至右排序，那么每转移一条边，只需要调换该边2个点的位置

这题没给范围，但是必须用long long

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
using namespace std;
#define MAXN (1000+10)
#define INF (1000000000)
#define eps 1e-10
struct P
{
	int x,y;
	long long operator*(const P &b)
	{
		return (long long)x*b.y-(long long)b.x*y;
	}
	friend bool operator<(P a,P b){if (a.x^b.x)	return a.x<b.x;return a.y<b.y;}
}a[MAXN];
long long abs2(long long x){if (x>0) return x;return -x;}
int n,h[MAXN];
struct E
{
	int i,j;
	double k;
	E(){}
	E(int _i,int _j):i(_i),j(_j){if (a[i].x==a[j].x) k=1e10;else k=(double)(a[i].y-a[j].y)/(a[i].x-a[j].x);}
	friend bool operator<(E a,E b){return a.k<b.k;	}
}e[MAXN*MAXN/2];
long long S2(P A,P B,P C)
{
	return abs2(A*B+B*C+C*A);
}
int size=0;
int main()
{
	freopen("land.in","r",stdin);
	freopen("land.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	long long ans=(long long)1<<60;
	/*
	for (int i=1;i<=n-2;i++)
		for (int j=i+1;j<n;j++)
			for (int k=j+1;k<=n;k++)
				ans=min(ans,abs2(a[i]*a[j]+a[j]*a[k]+a[k]*a[i]));
	*/

	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++) h[i]=i;
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++)
		{
			e[++size]=E(i,j);
		}

	sort(e+1,e+1+size);

	for (int i=1;i<=size&&ans;i++)
	{
		if (h[e[i].i]>1&&h[e[i].i]<n) ans=min(ans,S2(a[h[e[i].i]-1],a[h[e[i].i]],a[h[e[i].i]+1]));
		if (h[e[i].j]>1&&h[e[i].j]<n) ans=min(ans,S2(a[h[e[i].j]-1],a[h[e[i].j]],a[h[e[i].j]+1]));
		swap(a[h[e[i].i]],a[h[e[i].j]]);
		swap(h[e[i].i],h[e[i].j]);
	}

	printf("%.2lf",(double)ans/2);
	return 0;
}

CF 286B(Shifting-deque)

Posted on 24 3 月, 2013 by nike0good

John Doe has found the beautiful permutation formula.

Let's take permutation p = p₁, p₂, ..., p_n.
Let's define transformation f of this permutation:

k (k > 1) 是每段长度, r 是最大满足 rk ≤ n 的整数
把 r
段和尾剩余部分（如果有）左移.

求序列 f(f( ... f(p = [1, 2, ..., n], 2) ... , n - 1), n) .

Input

一行 n (2 ≤ n ≤ 10⁶).

Output

Print n distinct space-separated integers from 1 to n —
a beautiful permutation of size n.

Sample test(s)

input
2

output
2 1

input
3

output
1 3 2

input
4

output
4 2 3 1

Note

A note to the third test sample:

f([1, 2, 3, 4], 2) = [2, 1, 4, 3]
f([2, 1, 4, 3], 3) = [1, 4, 2, 3]
f([1, 4, 2, 3], 4) = [4, 2, 3, 1]

这题我是用WJMZBMR的神模拟过的。

先普及一下deque< >

deque<int> deq; //建立双端队列

deq.push_back(x)

deq.push_front(x)

deq.pop_back(x)

然后可以模拟了，每次把每段的最后搬上来。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define MAXN (1000000+10)
deque<int> deq;
int n;
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) deq.push_back(i);
	for (int i=2;i<=n;i++)
	{
		int l=(n-1)/i*i;deq.push_back(deq[l]);
		while (l-i>=0)
		{
			deq[l]=deq[l-i];
			l-=i;
		}
		deq.pop_front();
	}
	for (int i=0;i<deq.size();i++) cout<<deq[i]<<' ';
	return 0;
}

CF 286A(Lucky Permutation-数列找规律)

Posted on 23 3 月, 2013 by nike0good

A permutation p of size n is the sequence p₁, p₂, ..., p_n,
consisting of n distinct integers, each of them is from 1 to n (1 ≤ p_i ≤ n).

A lucky permutation is such permutation p, that any integer i (1 ≤ i ≤ n) meets
this condition p_p_i = n - i + 1.

You have integer n. Find some lucky permutation p of
size n.

Input

The first line contains integer n (1 ≤ n ≤ 10⁵)
— the required permutation size.

Output

Print "-1" (without the quotes) if the lucky permutation p of size n doesn't
exist.

Otherwise, print n distinct integers p₁, p₂, ..., p_n (1 ≤ p_i ≤ n) after
a space — the required permutation.

If there are multiple answers, you can print any of them.

Sample test(s)

input
1

output
1

input
2

output
-1

input
4

output
2 4 1 3

input
5

output
2 5 3 1 4 

找规律

如图所示

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iostream>
using namespace std;
int n;
int main()
{
	cin>>n;
	if (n%4>1)
	{
		cout<<"-1n";
		return 0;
	}
	for (int i=1;i<=n/2;i++)
	{
		if (i%2) cout<<i+1<<' ';
		else cout<<(n-i+2)<<' ';
	}
	int m=n/2;
	if (n%4==1)
	{
		cout<<m+1;
		if (m+1<n) cout<<' ';
		m++;
	}
	for (int i=m+1;i<n;i++)
	{
		if ((i-m)%2) cout<<n-i<<' ';
		else cout<<i-1<<' ';
	}
	if (m+1<n) cout<<(n-1);
	cout<<endl;
	return 0;
}

CF 287B(Pipeline-二分)

Posted on 23 3 月, 2013 by nike0good

Vova, the Ultimate Thule new shaman, wants to build a pipeline. As there are exactly n houses in Ultimate Thule, Vova wants the city to have exactly n pipes,
each such pipe should be connected to the water supply. A pipe can be connected to the water supply if there's water flowing out of it. Initially Vova has only one pipe with flowing water. Besides, Vova has several splitters.

A splitter is a construction that consists of one input (it can be connected to a water pipe) and x output pipes. When a splitter is connected to a water
pipe, water flows from each output pipe. You can assume that the output pipes are ordinary pipes. For example, you can connect water supply to such pipe if there's water flowing out from it. At most one splitter can be connected to any water pipe.

The figure shows a 4-output splitter

Vova has one splitter of each kind: with 2, 3, 4,
..., k outputs. Help Vova use the minimum number of splitters to build the required pipeline or otherwise state that it's impossible.

Vova needs the pipeline to have exactly n pipes with flowing out water. Note that some of those pipes can be the output pipes of the splitters.

Input

The first line contains two space-separated integers n and k (1 ≤ n ≤ 10¹⁸, 2 ≤ k ≤ 10⁹).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams
or the %I64dspecifier.

Output

Print a single integer — the minimum number of splitters needed to build the pipeline. If it is impossible to build a pipeline with the given splitters, print -1.

Sample test(s)

input
4 3

output
2

input
5 5

output
1

input
8 4

output
-1

这题显然优先找大的

直到找不下去了，判断无解或者拿个与需要的分水器相等的（显然有）

因为一个k的分水器只能增加k-1条通道

所以列方程

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iostream>
using namespace std;
#define MAXN (1000000000000000000)
#define MAXK (1000000000)
long long n,k;
long long bin_s(long long l,long long r)
{
	if (n==1) return 0;
	while (r-l>1)
	{
		long long  m=(l+r)/2;
		if ((m+k-1)*(k-m)>2*(n-1)) l=m;
		else r=m;
	}
	if ((l+k-1)*(k-l)>2*(n-1)) l=r;
	if ((l+k-1)*(k-l)<2*(n-1)) l--;

	if (l==0) return -1;
	return k-l;
}
int main()
{
	cin>>n>>k;
	cout<<bin_s(1,k-1)<<endl;


	return 0;
}

CF 287A(IQ Test-枚举3个字符相等的矩阵)

Posted on 23 3 月, 2013 by nike0good

In the city of Ultima Thule job applicants are often offered an IQ test.

The test is as follows: the person gets a piece of squared paper with a 4 × 4 square painted on it. Some of the square's cells are painted black and others are painted
white. Your task is to repaint at most one cell the other color so that the picture has a 2 × 2 square,
completely consisting of cells of the same color. If the initial picture already has such a square, the person should just say so and the test will be completed.

Your task is to write a program that determines whether it is possible to pass the test. You cannot pass the test if either repainting any cell or no action doesn't result in a 2 × 2 square,
consisting of cells of the same color.

Input

Four lines contain four characters each: the j-th character of the i-th
line equals "." if the cell in the i-th row and the j-th
column of the square is painted white, and "#", if the cell is black.

Output

Print "YES" (without the quotes), if the test can be passed and "NO"
(without the quotes) otherwise.

Sample test(s)

input
####
.#..
####
....

output
YES

input
####
....
####
....

output
NO

Note

In the first test sample it is enough to repaint the first cell in the second row. After such repainting the required 2 × 2 square is on the intersection of the 1-st
and 2-nd row with the 1-st and 2-nd
column.

枚举看是否有一个矩形有3个字符相等

一开始居然把4个判断打错了？《上午也是……

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
using namespace std;
#define MAXLen (4+10)
char a[MAXLen][MAXLen];
bool flag=0;
int main()
{
	for (int i=1;i<=4;i++) scanf("%s",a[i]+1);
	for (int i=1;i<4;i++)
		for (int j=1;j<4;j++)
		{
			if (a[i][j]==a[i][j+1]&&a[i][j]==a[i+1][j]) flag=1;
			if (a[i][j]==a[i][j+1]&&a[i][j]==a[i+1][j+1]) flag=1;
			if (a[i][j]==a[i+1][j]&&a[i][j]==a[i+1][j+1]) flag=1;
			if (a[i+1][j]==a[i][j+1]&&a[i+1][j]==a[i+1][j+1]) flag=1;

		}
	if (flag) printf("YESn");
	else printf("NOn");
	return 0;
}

银河之星(记忆化搜索+9点染色)

Posted on 23 3 月, 2013 by nike0good

Problem 3 银河之星(galaxy.cpp/c/pas)

数据组数不超过10.

这题就是记忆化搜索

9点染色减少状态，map记忆化

b[i][j][k]表示棋子可否从k方向到(i,j)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<map>
using namespace std;
#define MAXN (100+10)
#define MAXK (10+10)
#define MAXDIV (4)
int k,n,m,x2,y2,a[MAXDIV][MAXDIV],b[MAXDIV][MAXDIV][9];
int c[8][2]={{0,1},{0,2},{1,0},{2,0},{1,1},{2,2},{1,2},{2,1}};  //↑↓→←↗↙↘↖
map<long long,int> h;
bool is_ok()
{
	int ans=0;
	for (int i=0;i<3;i++)
		for (int j=0;j<3;j++)
			ans=(11*ans+a[i][j]);
	if (h.find(ans)!=h.end()) return 0;
	return h[ans]=1;
}
bool dfs(int x)
{
	/*
	for (int j=3;j;j--)
		{
			for (int i=1;i<=3;i++)
				cout<<a[i%3][j%3];
			cout<<endl;
		}
		cout<<endl;
	*/
	if (!is_ok()) return 0;
	if (x==1)
	{
		if (a[x2][y2]) return 1;
		else return 0;
	}
	for (int i=0;i<3;i++)
		for (int j=0;j<3;j++)
			if (a[i][j])
			{
				for (int l=0;l<8;l++)
					if (a[(i+c[l][0])%3][(j+c[l][1])%3]&&a[(i+2*c[l][0])%3][(j+2*c[l][1])%3]<b[(i+2*c[l][0])%3][(j+2*c[l][1])%3][l])
					{
						a[i][j]--;a[(i+c[l][0])%3][(j+c[l][1])%3]--;a[(i+2*c[l][0])%3][(j+2*c[l][1])%3]++;
						if (dfs(x-1)) return 1;
						a[i][j]++;a[(i+c[l][0])%3][(j+c[l][1])%3]++;a[(i+2*c[l][0])%3][(j+2*c[l][1])%3]--;

					}
			}
	return 0;
}
int main()
{
	freopen("galaxy.in","r",stdin);
	freopen("galaxy.out","w",stdout);
	while (scanf("%d%d%d%d%d",&k,&n,&m,&x2,&y2)!=EOF)
	{
		x2%=3;y2%=3;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		for (int i=0;i<3;i++)
			for (int j=0;j<3;j++)
			{
				int h=((n/3)+(i>0)*(i<=n%3)),r=((m/3)+(j>0)*(j<=m%3));
				//b[i][j][8]=((n/3)+(i>0)*(i<=n%3))*((m/3)+(j>0)*(j<=m%3));
				b[i][j][8]=h*r;
				if (j!=0) b[i][j][0]=max(r-1,0)*h;else b[i][j][0]=r*h;
				if ((m+1)%3!=j) b[i][j][1]=max(r-1,0)*h;else b[i][j][1]=r*h;
				if (i!=0) b[i][j][2]=max(h-1,0)*r;else b[i][j][2]=r*h;
				if ((n+1)%3!=i) b[i][j][3]=max(h-1,0)*r;else b[i][j][3]=r*h;
				b[i][j][4]=max(r-(j!=0),0)*max(h-(i!=0),0);
				b[i][j][5]=max(r-((m+1)%3!=j),0)*max(h-((n+1)%3!=i),0);
				b[i][j][6]=max(r-((m+1)%3!=j),0)*max(h-(i!=0),0);
				b[i][j][7]=max(r-(j!=0),0)*max(h-((n+1)%3!=i),0);
			}

		for (int i=1;i<=k;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			a[x%3][y%3]++;
		}
		/*
		for (int j=3;j;j--)
		{
			for (int i=1;i<=3;i++)
				cout<<a[i%3][j%3];
			cout<<endl;
		}
		cout<<endl;
		*/
		if (dfs(k)) cout<<"Yesn";
		else cout<<"Non";
		h.clear();
	}
	return 0;
}

BZOJ 1084([SCOI2005]最大子矩阵-长矩阵Dp)

Posted on 22 3 月, 2013 by nike0good

1084: [SCOI2005]最大子矩阵

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 586 Solved: 275
[Submit][Status][Discuss]

Description

这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。

Input

第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。

Output

只有一行为k个子矩阵分值之和最大为多少。

Sample Input

3 2 2

1 -3

2 3

-2 3

Sample Output

由于m不超过2

可以暴力Dp

分为m=1和m=2种情况

m=1就不用说了，

F[i][j][k]表示第1行到i第二行到j所能取到的最小值

#include<cstdio>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define MAXN (100+10)
#define MAXM (2+1)
#define MAXK (10+1)
int f[MAXN][MAXK],F[MAXN][MAXN][MAXK],n,m,k;
int a[MAXN][MAXN],sum[MAXN][MAXN];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	sum[0][1]=sum[0][2]=0;
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]),sum[i][j]=sum[i-1][j]+a[i][j];
	if (m==1)
	{
		memset(f,0,sizeof(f));
		for (int i=1;i<=n;i++)
		{
			f[i][0]=0;
			for (int l=1;l<=k;l++)
			{
				f[i][l]=f[i-1][l];
				for (int j=0;j<i;j++)
				{
					f[i][l]=max(f[i][l],f[j][l-1]+sum[i][1]-sum[j][1]);
				}
			}
		}
		cout<<f[n][k]<<endl;
	}
	else
	{
		memset(F,0,sizeof(F));
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=n;j++)
			{
				F[i][j][0]=0;
				for (int l=1;l<=k;l++)
				{
					F[i][j][l]=max(F[i-1][j][l],F[i][j-1][l]);
					for (int i2=0;i2<i;i2++) F[i][j][l]=max(F[i][j][l],F[i2][j][l-1]+sum[i][1]-sum[i2][1]);
					for (int j2=0;j2<j;j2++) F[i][j][l]=max(F[i][j][l],F[i][j2][l-1]+sum[j][2]-sum[j2][2]);
					if (i==j)
						for (int j2=0;j2<i;j2++)
						{
							F[i][i][l]=max(F[i][i][l],F[j2][j2][l-1]+sum[i][1]-sum[j2][1]+sum[j][2]-sum[j2][2]);
						}
				}
			}
		}

		cout<<F[n][n][k]<<endl;

	}


	return 0;
}

2026 年 4 月
一	二	三	四	五	六	日
		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