首页 > 其他 > 详细

浙江省 2015 省赛 D Beauty of Array dp

时间:2015-04-25 19:51:04      阅读:125      评论:0      收藏:0      [点我收藏+]
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;
long long int dp[100005];
int a[100005];
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
				
		scanf("%d",&n);
		map<int,int> num; //num记录前一个a[i]的位置 
		
		for(int i = 0;i < n;i++){
			scanf("%d",&a[i]);
			num[a[i]] = 0;	 
		}
		dp[0] = 0;
		dp[1] = a[0];
		num[a[0]] = 1;
		
		for(int i = 1;i < n;i++){
			/*
				dp[i] 为前i个美丽的数组的和
				前i个和包括前i-1个的和 dp[i-1] 还有由第i个数组成的和 dp[i] - dp[i-1] + a[i] * (i+1 - num[a[i]]);
				其中的i+1 - num[a[i]] 是用于去除重复的a[i],重复的只计算一次 
			*/ 
			dp[i+1] = dp[i] + dp[i] - dp[i-1] + a[i] * (i+1 - num[a[i]]);
			num[a[i]] = i+1; //将新的位置记录下来 
		}
		cout << dp[n] << endl;
	}
	return 0;
}

浙江省 2015 省赛 D Beauty of Array dp

原文:http://blog.csdn.net/qq_24667639/article/details/45272833

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!