链接

https://ac.nowcoder.com/acm/contest/75771/D

题解

本质为：1~a[m]中取部分数字为正数，部分为负数，相加得到n的倍数
思路：由数据范围可知，dp[N][N]可行
记dp[i][j]为第i轮变换后，能否到达j位置，可以为1，不可为0
lst 表示i-1轮可能的位置
用max实现有1为1
----------
亮点：在环上操作时喜欢0 ~ n-1 因为这样可以实现取模，取模结果都在这个范围里；

链接

https://codeforces.com/problemset/problem/455/A

题解

思路：看数据范围为1e5，且求最大值，联想到dp
dp[i]从小到大删除，删除i及其之前数的最大值；
cnt[i] 表示值为i的数的个数
如果i被删除，则dp[i] = dp[i-2] + cnt[i] * i;
如果i没有被删除，则dp[i] = dp[i - 1];
所以转移方程为dp[i] = max(dp[i-1],dp[i-2]+cnt[i] * i);