2014
03-01

# Aqua Splash

Recently a game named Aqua Splash attracted ZWC especially. The way to play the game is simple:
Give you a n*n chessboard. At first there are some blisters(水泡) on some position of the chessboard. There are three kinds of blisters. They will contain 1, 2 or 3 globules(水珠).

Now ZWC can choose one grid which has a blister to click. When being clicked, the blister will add one globule. If the number of globules in one blister is not less than 4, the blister will burst and disappear. Meanwhile, it will splash into 4 globules to up, down, left, right direction. In each direction, the first blister that not burst will absorb the globule and its globules will add one. This action may cause new blisters’ burst. If all the blisters have burst, ZWC will win the game.

To simplify this problem, you may suppose the globules move very fast and every second divide into two parts, at first all blisters have not less than 4 globules will burst and splash globules. Then the blisters still not burst try to absorb these globules. The following second repeats the same action.
You can get more detailed information from the sample.

ZWC wants to know whether he could win the game by clicking only one of the blisters. Can you help him?

The first line of the input is a single integer T which means the number of test cases.
Each test case starts with a line contains three numbers n (0 < n <= 20), the size of chessboard, x, y (1 <= x, y <= n) the grid that ZWC has clicked. Then n lines follow, each contains n integers. The integer aij (0<=aij <4) indicates the ith row and jth column of the chessboard has a blister with aij globules, aij = 0 means there isn’t exist a blister.

The first line of the input is a single integer T which means the number of test cases.
Each test case starts with a line contains three numbers n (0 < n <= 20), the size of chessboard, x, y (1 <= x, y <= n) the grid that ZWC has clicked. Then n lines follow, each contains n integers. The integer aij (0<=aij <4) indicates the ith row and jth column of the chessboard has a blister with aij globules, aij = 0 means there isn’t exist a blister.

2
4 4 4
0 3 0 0
3 3 0 3
0 0 0 0
0 3 0 3
4 3 3
3 1 0 0
3 1 2 3
2 3 3 3
0 0 2 3

Case 1: Yes! Good job ZWC!
Case 2: No! Please try again ZWC!
Hint
In the first Case, the first burst blister is at (4, 4), and (4, 2) and (2, 4) are at second 2, (2, 2) are at second 3, (1, 2) and (2, 1) are at second 4. In the second Case, (3, 3) is at second 1, (3, 2) and (3, 4) are at second 2, (2, 4) (3, 1) (4, 4) are at second 3, (2, 1) (2, 3) (4, 3) are at second 4, (1, 1) and (2, 2) are at second 5. the blister at (1, 2) will not burst.

# Discover’s Problem I

Submitted : 31, Accepted : 14

Given a sequence , how to find the longest increasing subsequence? I think, almost all of you will think it’s a piece of cake. Here comes a question about the increasing subsequence, and I think you will like it. Now you don’t need to pay attention to the
length but to the sum of its elements. You should find out the increasing subsequence that the sum of its elements is max and print the sum of this increasing subsequence’s elements.

## Input

The first line contains a integer T, indicating there a T cases(T<=10). Every case begin with a integer n, which is the length of the sequence. ( 1<=n<=10^5).The next line comes the elements . The values of it’s elements are positive integers that no more
than 2^31-1.

## Output

For every case, print the answer in a single line.

2
5
100 1 2 2 3
5
9 3 4 10 5

## Sample output

100
19

1.设结构体，包含两个变量：数值，下标

2.按照数值从小到大的规则排序

3.遍历排序后的序列，按照结构体中的下标插入树状数组中：求出树状数组中插入位置前的最大的递升序列和，加上当前结构体中的数值再插入

4.遍历求出最大值关键是树状数组如何操作，下面还是不理解记住吧！

/*
* File:   main.cpp
*
* Created on 2012年3月11日, 下午6:21
*/

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 100001;
long long a[MAX];
long long dp[MAX];

/*
* 这个是DP的思想，但是要实现DP还需一定的技巧
*/
int lowbit(int x) {
return x & (-x);
}

void add(int x, long long p) {
while (x < 100001) {
a[x] = max(p, a[x]);
x += lowbit(x);
}
}

long long sum(int x) {
long long res = 0;
while (x) {
res = max(res, a[x]);
x -= lowbit(x);
}
return res;
}

struct node {
int pos;
int element;

bool operator<(const node & a)const {
if (element != a.element) {
return element < a.element;
}
return pos > a.pos;
}
} Node[MAX];

int main() {
int T;
int n;
while (scanf("%d", &T) != EOF) {
while (T–) {
scanf("%d", &n);
memset(dp, 0, sizeof (dp));
memset(a, 0, sizeof (a));
for (int i = 1; i <= n; i++) {
scanf("%d", &Node[i].element);
Node[i].pos = i;
}
sort(Node + 1, Node + n + 1);
for (int i = 1; i <= n; i++) {
dp[Node[i].pos] = sum(Node[i].pos) + (long long)(Node[i].element);
}
long long res = 0;
for (int i = 1; i <= n; i++) {
res = max(dp[i], res);
}
printf("%lld\n", res);
}
}
return 0;
}

1. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. bottes vernies blanches

I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!