列表

详情

NC15335. Get the Highest Score

描述

First of all, I want to introduce a method of compressing the array to you. For an array A, we can compress it into the following form: (c1, v1) , (c2, v2) , ..., (cm, vm). It means that the value of the first c1 elements of the array A is v1, the value of the next c2 elements is v2, and so on.

For arbitrary i ∈ [1, m − 1], if it satisfies that vi ≠ vi+1, we think this compression method is “complete compression”. Otherwise, we think this compression method is “incomplete compression”.

There is an example of “complete compression”:

[100,100,−1,3,4,4] ⇒ (2,100),(1,−1),(1,3),(2,4) 
And there is an example of “incomplete compression”:

[10,10,4,4] ⇒ (2,10),(1,4),(1,4)

You can choose an arbitrary compression method to compress the array A, and the score of this compression method is:

Today, Jelly gets an array A of length N. Jelly will execute the following three steps in order: Firstly, he can replace some (or all of) “−1” in the array to arbitrary integer he wants. Secondly, he can choose an arbitrary compression method to compress the array.
Thirdly, he will calculate the score of this compression method.

Jelly wants to know the highest score that he can get. Jelly is too busy, so he wants you for help.

输入描述

The first line contains an integer T, where T is the number of test cases. T test cases follow. 
For each test case, the first line contains one integer N, where N is the length of the array A. 
The second line contains N integers A1, A2, ... , AN.  
• 1 ≤ T ≤ 105.
• 1 ≤ N ≤ 105.
• −1≤Ai ≤106.
• the sum of N in all test cases doesn’t exceed 106.

输出描述

For each test case, print one line containing “Case #x: y”, where x is the test case number (starting from
1) and y is the highest score that Jelly can get.

示例1

输入: 

2
9
0 1 1 0 0 -1 1 1 1
3
1 -1 -1

输出: 

Case #1: 25
Case #2: 9

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 473ms, 内存消耗: 2656K, 提交时间: 2018-12-07 01:22:23 

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

int main() {
	int Test;
	cin >> Test;
	for (int test = 1; test <= Test; ++test) {
		int n;
		cin >> n;
		vector<int> a(n + 1, -2);
		for (int i = 1; i <= n; ++i) {
			cin >> a[i];
		}
		vector<ll> dp(n + 1, 0);
		
		int curIndex = 0;
		ll curLen = 0;
		ll prevLen = 0;
		
		for (int i = 1; i <= n; ++i) {
			if (a[i] == -1) ++curLen;
			else {
				if (a[i] != a[curIndex]) {
					curIndex = i;
					prevLen = curLen;
				}
				curLen = 0;
			}
			
			if (curIndex == 0) dp[i] = curLen * curLen;
			else {
				ll len = i - curIndex + 1;
				ll t1 = dp[curIndex - 1] + len * len;
				ll t2 = dp[curIndex - prevLen - 1] + (len + prevLen) * (len + prevLen);
				dp[i] = max(t1, t2);
			}
		}

		cout << "Case #" << test << ": " << dp[n] << endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 199ms, 内存消耗: 2020K, 提交时间: 2020-03-29 12:15:13 

#include<stdio.h>
#include<string.h>
typedef long long ll;
int n;
int a[100001];
ll dp[100001];
int main()
{
	int Test;
	scanf("%d",&Test);
	for(int test=1;test<=Test;++test)
	{
		scanf("%d",&n);
		a[0]=-2;
		for(int i=1;i<=n;++i)
		{
			scanf("%d",&a[i]);
		}
		int curIndex=0;
		ll curLen=0;
		ll prevLen=0;
		dp[0]=0;
		for(int i=1;i<=n;++i)
		{
			if(a[i]==-1) ++curLen;
			else
			{
				if(a[i]!=a[curIndex])
				{
					curIndex=i;
					prevLen=curLen;
				}
				curLen=0;
			}
			if(curIndex==0) dp[i]=curLen*curLen;
			else
			{
				ll len=i-curIndex+1;
				ll t1=dp[curIndex-1]+len*len;
				ll t2=dp[curIndex-prevLen-1]+(len+prevLen)*(len+prevLen);
				dp[i]=t1>t2?t1:t2;
			}
		}
		printf("Case #%d: %lld\n",test,dp[n]);
	}
	return 0;
}

上一题

© 2025 nowcoder.com