首页 > ACM题库 > HDU-杭电 > HDU 3087-Aqua Splash-动态规划-[解题报告]HOJ
2014
03-01

HDU 3087-Aqua Splash-动态规划-[解题报告]HOJ

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(水珠).
Need for Speed

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. 

Sample Input 

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

Sample output

100
19

题目大意:给你一列数共n个(1<=n<=10^5),求最大的上升和序列。

分析:树状数组+DP 或则 线段树+DP现在我们先讲一下:树状数组+DP实际上状态转移方程是很容易想出的,dp[i]=max(dp[j])+a[i](其中0<j<i)关键是如何降低复杂度来实现快速的寻找最大的前i-1项中的最大上升和子序列。现在来说明一下如何用树状数组来实现快速的查询:按数的大小从小到大的排一下序,然后再按照数字的大小插入这样就保证了已经插入的就一定比插入的小,那么单调递增就能保证了,现在还一个需要确保,就是先后问题。由于树状数组如果按照排序前的序号插入的话,那么我们只统计他们的序号前面的就同样可以保证先后问题,仔细想一想其实没那么难的。

我们来寻找一下此问题的本源思想。我们是求上升且最大的子序列和,那么问题来了上升且最大,二这两个又不是单调的关系,无论怎样我们的快速查找的方法都只是一个排序的标准即一个判断条件。因此我们就想办法了,如果先确定一个不就OK了,寻找区间最大的方法是有的,因此我们就想方法先把单调升序列确定,然后查询区间的最大值。让序列在查询的过程中保持升序列的确很难想,现在介绍一下实际具体的做法:

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

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

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

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

代码如下

/*
 * File:   main.cpp
 * Author: Administrator
 *
 * 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);
                add(Node[i].pos, dp[Node[i].pos]);
            }
            long long res = 0;
            for (int i = 1; i <= n; i++) {
                res = max(dp[i], res);
            }
            printf("%lld\n", res);
        }
    }
    return 0;
}

 

 

参考:http://blog.csdn.net/cyb6100300115/article/details/7343050


  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!