[关闭]
@Acqua 2019-01-17T07:23:04.000000Z 字数 832 阅读 1078

免费馅饼(Jan. 17th, 2019)

动态规划

题目来源

题意

显然,见题目。

思路

以时刻和位置进行递推,设时刻为,位置为时有个馅饼下落,递推方程:

其中可压维,问题仅出在对的计算。
更新:用与数组等大的数组记录

反思

  1. 准确估算时间复杂度和空间复杂度,不要做出没有根据的怀疑。
  2. 做过的题要找时间复习,不要让它们烂在案卷里。

代码

  1. // La Pluie
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<algorithm>
  6. using namespace std;
  7. const int N = 1e5 + 5;
  8. int dp[2][15], temps[N][15];
  9. int main(){
  10. int n;
  11. while(~scanf("%d", &n) && n){
  12. memset(temps, 0, sizeof(temps));
  13. int tout = 0; memset(dp, -127, sizeof(dp));
  14. for(int i = 1; i <= n; i++){
  15. int x, tu;
  16. scanf("%d %d", &x, &tu);
  17. temps[tu][x]++;
  18. tout = max(tu, tout);
  19. }
  20. dp[0][5] = 0;
  21. int ans = 0;
  22. for(int i = 1; i <= tout; i++){
  23. for(int j = 0; j <= 10; j++){
  24. int aim = -1e9;
  25. if(j > 0) aim = max(aim, dp[(i - 1) & 1][j - 1]);
  26. if(j < 10) aim = max(aim, dp[(i - 1) & 1][j + 1]);
  27. dp[i & 1][j] = max(dp[(i - 1) & 1][j], aim) + temps[i][j];
  28. ans = max(ans, dp[i & 1][j]);
  29. }
  30. }
  31. printf("%d\n", ans);
  32. }
  33. return 0;
  34. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注