Online Datacenter Cloud Post : PUBLIC STAT 2 KB

INFO-- cont 1 file x1 .cpp

  • clock.cpp 1860 bytes

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;

struct clock
{
	int a,b,c,d,e,f,g,h,i;
	string l;
	void operator=(clock ot)
	{
		a=ot.a;b=ot.b;c=ot.c;d=ot.d;e=ot.e;f=ot.f;g=ot.g;h=ot.h;i=ot.i;l=ot.l;
	}
} queue[1000000];

typedef struct clock clock;

inline clock m1(clock a){return {++a.a%4,++a.b%4,  a.c,  ++a.d%4,++a.e%4,  a.f,    a.g,    a.h,    a.i,    a.l+"1 "};}
inline clock m2(clock a){return {++a.a%4,++a.b%4,++a.c%4,  a.d,    a.e,    a.f,    a.g,    a.h,    a.i,    a.l+"2 "};}
inline clock m3(clock a){return {  a.a  ,++a.b%4,++a.c%4,  a.d,  ++a.e%4,++a.f%4,  a.g,    a.h,    a.i,    a.l+"3 "};}
inline clock m4(clock a){return {++a.a%4,  a.b,    a.c,  ++a.d%4,  a.e,    a.f,  ++a.g%4,  a.h,    a.i,    a.l+"4 "};}
inline clock m5(clock a){return {  a.a,  ++a.b%4,  a.c,  ++a.d%4,++a.e%4,++a.f%4,  a.g,  ++a.h%4,  a.i,    a.l+"5 "};}
inline clock m6(clock a){return {  a.a,    a.b,  ++a.c%4,  a.d,    a.e,  ++a.f%4,  a.g,    a.h,  ++a.i%4,  a.l+"6 "};}
inline clock m7(clock a){return {  a.a,    a.b,    a.c,  ++a.d%4,++a.e%4,  a.f,  ++a.g%4,++a.h%4,  a.i,    a.l+"7 "};}
inline clock m8(clock a){return {  a.a,    a.b,    a.c,    a.d,    a.e,    a.f,  ++a.g%4,++a.h%4,++a.i%4,  a.l+"8 "};}
inline clock m9(clock a){return {  a.a,    a.b,    a.c,    a.d,  ++a.e%4,++a.f%4,  a.g,  ++a.h%4,++a.i%4,  a.l+"9 "};}

clock(*arr[9])(clock) = {m1,m2,m3,m4,m5,m6,m7,m8,m9};
string bfs(clock s)
{
	int h=0,t=0;
	queue[t++]=s;
	while(h!=t)
	{
		clock p=queue[h++];
		if(p.a==0&&p.b==0&&p.c==0&&p.d==0&&p.e==0&&p.f==0&&p.g==0&&p.h==0&&p.i==0) return p.l;
		for(auto f:arr) queue[t++] = f(p);
	}
	return "NO";
}

int main()
{
	clock a;
	scanf("%d %d %d %d %d %d %d %d %d",&a.a,&a.b,&a.c,&a.d,&a.e,&a.f,&a.g,&a.h,&a.i);
	string s=bfs(a); s.erase(s.end()-1,s.end());
	cout<<s<<endl;
}

Reason: Test on other computer for CE

NOIP 2012 Group 1: Arrange Flowers

NOIP 2012 Group 1: Arrange Flowers

My Translation

N types of flowers are to be put into M ordered pots. The _i_th type only has A(i) flowers bought. Also, all flowers of the _i_th type must come before all flowers of the _i+1_th type. Calculate the amount of total possible orderings.

The Algorithm

Being lazy to find the mathematical approach, the sentence "N types...[in] M...pots" reveals that this is a dynamic programming problem. However, the confusing part is how to actually count the possible amount of orderings. At each DP step, the counter increases by the Xth previous state of the counter where X is a number from 0 to the minimum of a[i] and j. This is because that the counter updates itself from the previous state to create an exponentially-increasing function, as we want. We set the state (i,j) (where i is how many flowers are currently introduced and j is how many pots are introduced) to the sum of all values of the states (i-1,j-1) (i-1,j-2) ... (i-1,0) because each represents putting a different number of plant number i.

NOIP 2010 Group 2: Tortoise Chess

NOIP 2010 Group 2: Tortoise Chess

Initial Problem

描述

小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数)。棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中M张爬行卡片,分成4种不同的类型(M张卡片中不一定包含所有4种类型的卡片,见样例),每种类型的卡片上分别标有1234四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次。
游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?
格式

输入格式

输入文件的每行中两个数之间用一个空格隔开。
12个正整数NM,分别表示棋盘格子数和爬行卡片数。
2N个非负整数,a1a2……aN,其中ai表示棋盘第i个格子上的分数。
3M个整数,b1b2……bM,表示M张爬行卡片上的数字。
输入数据保证到达终点时刚好用光M张爬行卡片。
输出格式

输出只有1行,1个整数,表示小明最多能得到的分数。
样例1

样例输入1

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
Copy
样例输出1

73
Copy
限制

每个测试点1s
提示

小明使用爬行卡片顺序为11312,得到的分数为6+10+14+8+18+17=73。注意,由于起点是1,所以自动获得第1格的分数6
对于30%的数据有1N301M12
对于50%的数据有1N1201M50,且4种爬行卡片,每种卡片的张数不会超过20
对于100%的数据有1N3501M120,且4种爬行卡片,每种卡片的张数不会超过400ai1001iN1bi41iM

My Translation

There is a 1-D grid of N cells, each with a whole number, or "point value" in them. There are also M cards, each consisting of either 1, 2, 3, or 4. In each "turn" you select one of the M cards to move a pointer the number indicated on the card steps forward. Then, that particular card is discarded. The process repeats until no cards are left. Then, the total points are calculated by summing the M+1 point values the pointer landed on. Calculate the maximum possible total points given all point values and all M cards.

The Algorithm

The sentence "each turn ... select one of the M cards ..." proposes that this is a DP problem, because any other naive method wouldbe of O(N^2). We can try making advantage of the fact that there is only 4 card possibilities. It is possible to track the amount of cards saying 1, 2, 3, or 4, and build up solutions from that. Because of 4 DP parameters (# of ones, twos, threes, and fours) the DP array must be 4-D with each dimension of the maximum possible number of ones, twos, threes, or fours. My code illustrates this example. If there was only 2 parameters, this would be roughly a 0-1 Knapsack Problem.

The Code

#include <cstdio>
#include <algorithm>
using namespace std;
int dp[41][41][41][41];
int num[4], board[401];

int main()
{
	int L, C; scanf("%d %d", &L, &C);
	for(int i=0;i<L;i++) scanf("%d",&board[i]);
	for(int i=0;i<C;i++)
	{
		int x; scanf("%d", &x);
		num[x-1]++;
	}
	for(int a=0;a<=num[0];a++)
		for(int b=0;b<=num[1];b++)
			for(int c=0;c<=num[2];c++)
				for(int d=0;d<=num[3];d++)
				{
					int t=0;
					if(a) t=max(t,dp[a-1][b][c][d]);
					if(b) t=max(t,dp[a][b-1][c][d]);
					if(c) t=max(t,dp[a][b][c-1][d]);
					if(d) t=max(t,dp[a][b][c][d-1]);
					dp[a][b][c][d]=t+board[a+2*b+3*c+4*d];
				}
				
	printf("%d",dp[num[0]][num[1]][num[2]][num[3]]);
}

GitHub – testitem

Darren Li

New York City