做美女图片网站挣钱么/五年级下册数学优化设计答案

题目

UVALive 4764 Bing it

题意

给一副牌，开始时手里拿到第一张牌val[0]接下来依次遍历，对于每一个位置i，可以选择把手中的牌换成位置i的牌val[i],或者保持不变，若手中的牌与位置i的牌相同时，获得分数，面值为999时得3分，其余1分，求可能获得的最大分数

解法

dp[i]定义为在位置i获得的最大分数，用pre[i]标记面值为i的牌出现的最后的位置

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100100;
int val[N], pre[N], dp[N]; 
int main() {int n;while(scanf("%d", &n) && n) {for(int i = 0; i < n; i++)scanf("%d", val + i);memset(pre, -1, sizeof(pre));dp[0] = 0;pre[val[0]] = 0;for(int i = 1; i < n; i++) {if(pre[val[i]] == -1)dp[i] = dp[i - 1];elsedp[i] = max(dp[i - 1], dp[pre[val[i]]] + (val[i] == 999 ? 3 : 1));pre[val[i]] = i;}printf("%d\n", dp[n - 1]);}return 0;
}

来源

Regionals 2009 Asia Harbin

赛后总结

2015暑假训练赛团体赛（8.3）