CF455A
[TOC]
题意
给你长为 N 的整数序列a,你可以选择其中一个数ak,你会得到与这个数相同的分数,然后数列中和 ak+1 ak-1相同的数都会被删掉,求最多的分数
输入
第一行给出一个n
接下来在一行中给出 n个数,第i个数表示ai
输出
输出可得到的最多的分数
解析
这个题肯定是用哈希来表示每个数出现了多少次,然后自小到大遍历,决策.
但是我们发现一个数要么取要么不取,但是其取或者不取只取决于其前面那一个数,所以就自然地想到动态规划,也就是截止到这个数所能得到的最大的分数其实是由更小的区间的最多的分数决定的,也就意味着满足最优子结构性质,也就是可以动态规划解决
我们采用dp[i][j]来表示i被取的时候(j=0)和i不被取的时候(j=1)累计能得到的最大分数
显然我们发现两个状态转移方程
dp[i][0] = i*a[i] + dp[i-1]dp[i][1] = max(dp[i-1][0],dp[i-1][1])
即第i位能选的情况只能是第i-1位没选的时候,也就是dp[i-1][0]再加上i*a[i] 即此位带来的贡献
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// CF1034A
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
void ioInit() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
unsigned long long a[100100];
unsigned long long dp[100100][2];
unsigned long long myMax(unsigned long long a, unsigned long long b) {
if (a > b) {
return a;
}
return b;
}
int main() {
long long n;
cin >> n;
int maxn = 0;
for (int i = 1; i <= n; ++i) {
int tmp;
cin >> tmp;
maxn = max(maxn, tmp);
++a[tmp];
}
for (unsigned long long j = 1; j <= maxn; ++j) {
// 0 表示选
// 1 表示不选
dp[j][0] = a[j] * j + dp[j - 1][1];
dp[j][1] = myMax(dp[j - 1][0], dp[j - 1][1]);
}
cout << (unsigned long long) myMax(dp[maxn][0], dp[maxn][1]) << endl;
return 0;
}
启示
虽然只是很简单的动态规划,但是我发现我的思路还是不是特别顺畅,特地看了一下排行榜,有一位韩国选手只用了一分钟就AC了…这个实在是给我很大震撼,在此特地将代码放出(注释是我加的)
大神代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<lint, lint> pi;
const int mod = 999983;
int n, a[100005];
// 仅用一维,dp[i]就表示[1,i]区间能获得的最大的分数
lint dp[100005];
int main(){
cin >> n;
while(n--){
int x;
cin >> x;
a[x]++;
}
for(int i=1; i<=100000; i++){
if(a[i]){
dp[i] = dp[i-2] + 1ll * a[i] * i;
}
dp[i] = max(dp[i], dp[i-1]);
// 这个地方实在是不太直观,甚至有些违反直觉
// 我是这样理解的
// 还是根据我的两个递推公式
// dp[j][0] = a[j] * j + dp[j - 1][1];
// dp[j][1] = myMax(dp[j - 1][0], dp[j - 1][1]);
// 我们如果强行用一维数组保存的话
// 我们就令 dp1[j] = max(dp[j][0],dp[j][1])
// 然后我们发现
// dp[j][1] = dp1[j-1]
// 换言之 dp[j-1][1] = dp1[j-2]
// 我们将其带入递推公式1,得到
// dp[j][0] = a[j]*j + dp1[j-2]
// 然后dp1[j] = max(dp[j][0],dp[j][1])
// 也就是 dp1[j] = max( a[j] * j +dp1[j-2] , dp1[j-1] )
// 我们发现式子中只剩下dp1了,也就是这个递推公式和之前的两个是等价的
// 这个非常的巧妙,难以想想大神是如何直接写出的
// 或者我们来正面分析一下
// dp1[j]的情况是怎么由其他情况得到的
// 第一种情况,dp1[j-2],无论j-2这个元素拿还是没拿,都不影响j的选择,也就是j一定拿
// 第二种情况,如果j不拿,那么它和dp1[j-1]的分数是相同的,这一步无论j-1拿没拿都不影响这个区间的分数.如果j-1拿了,反正j不拿,不会违反题意,如果j-1没拿,根据递推公式dp1[j-1]和 dp1[j-2]的分数是一样的,也就是一定会被dp1[j-2]+j*a[j]给比下去,仍然不违反题意,所以正着看也很巧妙
}
cout << dp[100000];
}
