首页 > ACM题库 > HDU-杭电 > hdu 3872-dragon ball-动态规划-[解题报告]hoj
2015
04-13

hdu 3872-dragon ball-动态规划-[解题报告]hoj

Dragon Ball
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65768/32768 K (Java/Others)
Total Submission(s): 113 Accepted Submission(s): 45

Problem Description
There are N "dragon balls" lined up into one row from left to right. Every dragon ball has two properties: the type and energy. We can cut these balls into some segments ( these segments should not be empty). You can not change the order of these balls. In
each segment, if there exists a ball which is not the right most one and its type is the same with the right most one ,this segment will explode. The energy of a segment is the energy of the ball with largest energy in this segment. Now please minimize the
total energy of all these segments without explosion.

Input
There will be T (T<=10) test cases. Each test case contains three lines. The first line comes an Integer N (1<=N<=100000), the number of dragon balls. The second line contains N integer numbers, indicating the type of the dragon balls. The types will be a number
between 1 and 100000. The last line of each case also contains N integer numbers, representing the energy of each ball. The energy will be positive and not greater than 1000000.

Output
For each case, print a line contains a number representing the minimum energy value.

Sample Input
2
6
5 1 3 1 2 1
6 5 1 3 4 2
3
1 1 1
2 2 2

Sample Output
8
6

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100001
int n;
int val[MAXN], type[MAXN];
int f[MAXN], d[MAXN];
int mark[MAXN];

int stack[MAXN], top;

struct Lnode{
	int fmin, smin, sbuf;
	int left, right;
}node[MAXN * 3];

int imin(int a, int b){
	return a < b ? a : b;
}

int imax(int a, int b){
	return a > b ? a : b;
}

void maketree(int root, int left, int right){
	if (left > right) return;
//	printf("maketree: root = %d, (%d, %d)\n", root, left, right);
	node[root].left = left;
	node[root].right = right;
	node[root].fmin = node[root].smin = 0x7fffffff;
	node[root].sbuf = -1;
	if (left == right) return;
	maketree(root * 2, left, (left + right) / 2);
	maketree(root * 2 + 1, (left + right) / 2 + 1, right);
}

int QueryF(int root, int left, int right){
	int mid = (node[root].left + node[root].right) / 2;
	int k;
//	printf("QueryF: root = %d\n", root);
	if (left <= node[root].left && right >= node[root].right)
		return node[root].fmin;
	if (left > right || node[root].left == node[root].right) return 0x7fffffff;
	k = 0x7fffffff;
	if (mid >= left) k = imin(k, QueryF(root * 2, left, imin(mid, right)));
	if (mid + 1 <= right) k = imin(k, QueryF(root * 2 + 1, imax(left, mid + 1), right));
	return k;
}

void modifyF(int root, int loc){
	int mid = (node[root].left + node[root].right) / 2;
//	printf("modifyF: root = %d, loc = %d\n", root, loc);
	if (node[root].left == loc && node[root].right == loc){
		node[root].fmin = f[loc];
	}else if (node[root].left == node[root].right){
		return;
	}else if (mid >= loc){
		modifyF(root * 2, loc);
		node[root].fmin = imin(node[root].fmin, node[root * 2].fmin);
	}else{
		modifyF(root * 2 + 1, loc);
		node[root].fmin = imin(node[root].fmin, node[root * 2 + 1].fmin);	
	}
}

int QueryS(int root, int left, int right){
	int mid = (node[root].left + node[root].right) / 2;
	int k;
//	printf("QueryS: root = %d, (%d, %d)\n", root, left, right);
	if (left <= node[root].left && right >= node[root].right)
		return node[root].smin;
	if (left > right || node[root].left == node[root].right) return 0x7fffffff;
	if (node[root].sbuf >= 0){
		node[root * 2].sbuf = node[root * 2 + 1].sbuf = node[root].sbuf;
		node[root * 2].smin = node[root * 2].fmin + node[root * 2].sbuf;
		node[root * 2 + 1].smin = node[root * 2 + 1].fmin + node[root * 2 + 1].sbuf;
		node[root].sbuf = -1;
	}
	k = 0x7fffffff;
	if (mid >= left) k = imin(k, QueryS(root * 2, left, imin(mid, right)));
	if (mid + 1 <= right) k = imin(k, QueryS(root * 2 + 1, imax(left, mid + 1), right));
	return k;
}

void modifyS(int root, int left, int right, int k){
	int mid = (node[root].left + node[root].right) / 2;
//	printf("modifyS: root = %d, (%d, %d) + %d\n", root, left, right, k);
	if (left <= node[root].left && right >= node[root].right){
		node[root].sbuf = k;
		node[root].smin = node[root].fmin + k;
	}else if (left > right || node[root].left >= node[root].right){
		return;
	}else{ 
		if (node[root].sbuf >= 0){
			node[root * 2].sbuf = node[root * 2 + 1].sbuf = node[root].sbuf;
			node[root * 2].smin = node[root * 2].fmin + node[root * 2].sbuf;
			node[root * 2 + 1].smin = node[root * 2 + 1].fmin + node[root * 2 + 1].sbuf;
			node[root].sbuf = -1;
		}
		if (mid >= left){
			modifyS(root * 2, left, imin(mid, right), k);
		}
		if (mid + 1 <= right){
			modifyS(root * 2 + 1, imax(left, mid + 1), right, k);
		}
		node[root].smin = imin(node[root * 2].smin, node[root * 2 + 1].smin);
	}
}

void calc(){
	int i, j, k;
	for (i = 1; i <= n; i++){
		d[i] = mark[type[i]];
		mark[type[i]] = i;
	}
//	stack[++top] = 1;
//	f[1] = val[1];
//	modifyF(1, 1);
	f[0] = 0;
	modifyF(1, 0);
	modifyS(1, 0, 0, 0);
	for (i = 1; i <= n; i++){
		while(top > 0 && val[stack[top]] <= val[i]) top--;
		stack[++top] = i;
		// t = stack[j - 1] + 1...stack[j]
		modifyS(1, stack[top - 1], stack[top] - 1, val[i]);
		
		f[i] = QueryS(1, d[i], i - 1);
		modifyF(1, i);
	}
}

int main(){
	int i, T;
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		for (i = 1; i <= n; i++) scanf("%d", &type[i]);
		for (i = 1; i <= n; i++) scanf("%d", &val[i]);
		memset(mark, 0, sizeof(mark));
		maketree(1, 0, n);
		stack[top = 0] = 0;
		calc();
		//for (i = 1; i <= n; i++)
		//	printf("%d ", f[i]);
		//printf("\n");
		printf("%d\n", f[n]);
	}
//	system("pause");
	return 0;
}

/********************
dp的状态方程都很好想
f[i]以i为结尾的最小值
f[i] = f[j] + min{val[j + 1]...val[i]}
但n是10^5,超时,需要优化
(以前从没对dp优化过...额,除了偶然接触的斜率优化...)
看了解题报告,按我的想法理解哈,维护个栈保证栈内元素
下标递增,val递减。例如计算f[i]时,将i加入栈
若stack[k - 1] <= j < stack[k], 则min{val[j + 1]..val[i]} = val[stack[k]]
这样每次考察区间stack[k - 1]..stack[k], 其中的min{val..}是相同的,
只要再找min{f[j]}就好了

于是可以维护线段树之类的快速查询min{f[j]}
写完,交上去跑了2400+ms...稳居页末...
又加上维护min{f[j] + min{val...}}的,就跑了1000+ms~比较满意了的说~
表示没咋写过高级一点数据结构...实现不太优美...缺练,恩...
*********************/

版权声明:本文为博主原创文章,未经博主允许不得转载。


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  3. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3