PDD 4.15笔试第一题

我是贪心的做法，嗯没考虑太多，然后AC了 #include <iostream> (30316)#include <algorithm> #include <cstring> using namespace std; int n; string str; int main() { cin >> n >> str; int res = n / 3; int cost = 1e9; for (int j = 0; j <= n % 3; j++) { int sum = 0; for (int i = j; i < n; i += 3) { if (i + 3 > n) break; sum += abs(str[i] - 'P') + abs(str[i + 1] - 'D') + abs(str[i + 2] - 'D'); } // cout << j << " " << sum << endl; cost = min(cost, sum); } cout << res << " " << cost; return 0; }

有说不能中间断开吗😱我也是考虑中间断开然后64

96不知道咋回事

我用的是dp的方法，贴一段代码，实在想不出来反例 int n; string s; int cost[100005]; int dp[100005][3]; int main() { cin >> n >> s; for (int i = 2; i < n; i++) { int c = 0; c += abs('P' - s[i - 2]); c += abs('D' - s[i - 1]); c += abs('D' - s[i]); cost[i] = c; } for (int i = 0; i <= n; i++) { for (int j = 0; j < 3; j++) { dp[i][j] = 10000000; } } int k = n % 3; dp[0][k] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { int x = dp[i][j]; // printf("%d %d %d\n",i,j,x); if (j - 1 >= 0) { dp[i + 1][j - 1] = min(dp[i + 1][j - 1], x); } if (j - 2 >= 0) { dp[i + 2][j - 2] = min(dp[i + 2][j - 2], x); } if (i + 3 <= n) { dp[i + 3][j] = min(dp[i + 3][j], x + cost[i + 2]); } } } cout << n / 3 << " " << dp[n][0] << endl; }

68

第一题啥题，做出来了，但是忘了题目是什么了

n^2只有64吗？