@Acqua
2019-01-17T07:23:04.000000Z
字数 832
阅读 1078
动态规划
显然,见题目。
以时刻和位置进行递推,设时刻为,位置为时有个馅饼下落,递推方程:
其中可压维,问题仅出在对的计算。
更新:用与数组等大的数组记录。
- 准确估算时间复杂度和空间复杂度,不要做出没有根据的怀疑。
- 做过的题要找时间复习,不要让它们烂在案卷里。
// La Pluie#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N = 1e5 + 5;int dp[2][15], temps[N][15];int main(){int n;while(~scanf("%d", &n) && n){memset(temps, 0, sizeof(temps));int tout = 0; memset(dp, -127, sizeof(dp));for(int i = 1; i <= n; i++){int x, tu;scanf("%d %d", &x, &tu);temps[tu][x]++;tout = max(tu, tout);}dp[0][5] = 0;int ans = 0;for(int i = 1; i <= tout; i++){for(int j = 0; j <= 10; j++){int aim = -1e9;if(j > 0) aim = max(aim, dp[(i - 1) & 1][j - 1]);if(j < 10) aim = max(aim, dp[(i - 1) & 1][j + 1]);dp[i & 1][j] = max(dp[(i - 1) & 1][j], aim) + temps[i][j];ans = max(ans, dp[i & 1][j]);}}printf("%d\n", ans);}return 0;}