1137
http://www.ifrog.cc/acm/problem/1137
和差化积公式，
变成2 * sin((x + y) / 2) * cos((x - y) / 2) + sin(n - (x + y))
然后很重要的一个就是cos(x) = cos(-x)
这样，枚举x + y的取值i，当x + y取值是i的时候，x - y的取值也是有固定的规律，具体就是
i是偶数的时候，0、2、...、这样吧
i是奇数的时候，1、3......、这样吧
然后就要分情况取值，
当sin((x + y) / 2)小于0，就要取一个min去和它乘，否则娶个大的，
数组开大了TLE，不是很懂。
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; double dp[2][2]; void work() { int n; scanf("%d", &n); dp[0][0] = dp[0][1] = 1; dp[1][0] = dp[1][1] = cos(0.5); double ans = -1.0; for (int i = 2; i <= n - 1; ++i) { double res = sin(i * 0.5); if (res < 0) { if (i & 1) { ans = max(ans, 2 * res * dp[1][0] + sin(n - i)); } else ans = max(ans, 2 * res * dp[0][0] + sin(n - i)); } else { if (i & 1) { ans = max(ans, 2 * res * dp[1][1] + sin(n - i)); } else ans = max(ans, 2 * res * dp[0][1] + sin(n - i)); } res = cos(i); dp[0][0] = min(dp[0][0], res); dp[0][1] = max(dp[0][1], res); dp[1][0] = min(dp[1][0], res); dp[1][1] = max(dp[1][1], res); } printf("%0.9f ", ans); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; const int maxn = 3e6 + 20; double dp[maxn][2]; void work() { int n; scanf("%d", &n); dp[0][0] = dp[0][1] = cos(0); dp[1][0] = dp[1][1] = cos(0.5); // for (int i = 2; i <= n; ++i) { // dp[i][0] = min(dp[i - 2][0], cos(i * 0.5)); // dp[i][1] = max(dp[i - 2][1], cos(i * 0.5)); // } double ans = -1.0; for (int i = 2; i <= n - 1; ++i) { double res = sin(i * 0.5); if (i & 1) { ans = max(ans, 2 * res * dp[i - 2][0] + sin(n - i)); } else { ans = max(ans, 2 * res * dp[i - 2][1] + sin(n - i)); } res = cos(i * 0.5); dp[i][0] = min(dp[i - 2][0], res); dp[i][1] = max(dp[i - 2][1], res); } printf("%0.9f ", ans); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }