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]}

（以前从没对dp优化过...额，除了偶然接触的斜率优化...）

*********************/