专业做医院网站建设,网站自己怎么建设,阿里云服务器12元一年,mysql做网站怎么查看数据库题目链接
CodeForce 455A. Boredom
思路
因为跟序列的下标无关#xff0c;所以先对数组a排个序。那么每次选择只会影响两侧的元素。
记号
令dp[i]dp[i]dp[i]表示排序后a[1..i]a[1..i]a[1..i]能够获得的最大点数。 但是这样不足以区分是否当前元素可以被使用#xff0c;所…题目链接
CodeForce 455A. Boredom
思路
因为跟序列的下标无关所以先对数组a排个序。那么每次选择只会影响两侧的元素。
记号
令dp[i]dp[i]dp[i]表示排序后a[1..i]a[1..i]a[1..i]能够获得的最大点数。 但是这样不足以区分是否当前元素可以被使用所以再开一个维度 令 dp[i][0]dp[i][0]dp[i][0]表示我们无法使用当前元素a[i]a[i]a[i]所获得的最大点数。 dp[i][1]dp[i][1]dp[i][1]表示我们使用当前元素a[i]a[i]a[i]能够获得的最大点数。 那么对相邻的两个元素讨论即可。
状态转移方程
对于a[i] a[i-1] 1 那么当前选择不会影响到之前的点数。所以 dp[i][1]max(dp[i−1][0],dp[i−1][1])a[i]dp[i][1] max(dp[i-1][0],dp[i-1][1]) a[i]dp[i][1]max(dp[i−1][0],dp[i−1][1])a[i] 对于a[i] a[i-1]1
若此时选择a[i]则与a[i-1]相等的都不能被选中。j是最大满足a[j] a[i-1]的下标j那么dp[i][1]dp[j]a[i]dp[i][1] dp[j] a[i]dp[i][1]dp[j]a[i]若此时不选择a[i]那么当然得选择a[i-1]才会更好。故dp[i][0]dp[i−1][1]dp[i][0]dp[i-1][1]dp[i][0]dp[i−1][1] 对于a[i] a[i-1]那么当a[i-1]不能被选择时a[i]也不能被选择。反之亦然。 故有dp[i][0]dp[i−1][0]dp[i][1]dp[i−1][1]a[i]dp[i][0]dp[i-1][0] \\dp[i][1] dp[i-1][1] a[i] dp[i][0]dp[i−1][0]dp[i][1]dp[i−1][1]a[i]
代码
#includebits/stdc.husing namespace std;typedef long long LL;
vectorLL a;int main() {int n;cin n;a.resize(n 1);for (int i 1; i n; i) {cin a[i];}sort(a.begin() 1, a.end());vectorvectorLL dp(n 1, vectorLL(2));dp[1][1] a[1];for (int i 2; i n; i) {if (a[i] a[i - 1] 1) {// dp[i][1]表示使用了当前元素dp[i][1] max(dp[i - 1][0], dp[i - 1][1]) a[i];} else {if (a[i] a[i - 1] 1) {// the prev of first element equal to a[i-1]int j lower_bound(a.begin() 1, a.begin() i, a[i - 1]) - a.begin() - 1;dp[i][1] max(dp[j][1], dp[j][0]) a[i];dp[i][0] dp[i - 1][1];} else if (a[i] a[i - 1]) {dp[i][0] dp[i - 1][0];dp[i][1] dp[i - 1][1] a[i];}}
// printf(dp[%d]%d\n, i, max(dp[i][0], dp[i][1]));}cout max(dp[n][0], dp[n][1]);
}
