解：这个题一脸不可做...
比1小的怎么办啊，好像没用，扔了吧。
先看部分分，n = 2简单，我会分类讨论！n = 4简单，我会搜索！n = 10，我会剪枝！
k = 1怎么办，好像选的那些越大越好啊，那么我就排序之后枚举后缀！
k = INF怎么办啊，好像最优策略是从小到大一个一个连通啊，那直接模拟好了。
写一写，有40分了。
别的怎么办啊，拿搜索找规律吧？于是发现一个规律(伪)：最优策略一定是单独选择最后k - 1个，和前面的一个后缀。
于是枚举后缀，然后模拟后面的部分，成功得到了61分！
1 #include2 3 // ---------- decimal lib start ---------- 4 5 // ---------- decimal lib end ---------- 6 7 const int N = 8010; 8 9 int n, k, p; 10 Decimal a[N]; 11 12 inline void output(Decimal x) { 13 std::cout << x.to_string(p + 5) << std::endl; 14 return; 15 } 16 17 inline void output(double x) { 18 printf("%.10f\n", x); 19 return; 20 } 21 22 inline void out(int x) { 23 for(int i = 0; i < n; i++) { 24 printf("%d", (x >> i) & 1); 25 } 26 return; 27 } 28 29 namespace bf { 30 31 const double eps = 1e-12; 32 33 double ans = 0, a[N], temp[101][101]; 34 int lm, pw[110101], Ans[N], now[N]; 35 36 void DFS(int x) { 37 /// check 38 double large(0); 39 for(int i = 1; i <= n; i++) { 40 if(large < a[i]) large = a[i]; 41 } 42 if(large < ans + eps) { 43 return; 44 } 45 if(fabs(large - a[1]) < eps || x > k) { 46 if(ans < a[1]) { 47 ans = a[1]; 48 memcpy(Ans + 1, now + 1, x * sizeof(int)); 49 } 50 return; 51 } 52 53 for(int i = 1; i <= n; i++) { 54 temp[x - 1][i] = a[i]; 55 } 56 for(int s = lm - 1; s > 1; s--) { 57 if(!(s - (s & (-s)))) continue; 58 double tot = 0; 59 int cnt = 0; 60 int t = s; 61 while(t) { 62 int tt = pw[t & (-t)] + 1; 63 tot += a[tt]; 64 cnt++; 65 t ^= 1 << (tt - 1); 66 } 67 tot /= cnt; 68 t = s; 69 while(t) { 70 int tt = pw[t & (-t)] + 1; 71 a[tt] = tot; 72 t ^= 1 << (tt - 1); 73 } 74 now[x] = s; 75 DFS(x + 1); 76 t = s; 77 while(t) { 78 int tt = pw[t & (-t)] + 1; 79 a[tt] = temp[x - 1][tt]; 80 t ^= 1 << (tt - 1); 81 } 82 } 83 now[x] = 0; 84 return; 85 } 86 87 inline void solve() { 88 89 /// DFS 90 lm = 1 << n; 91 for(int i = 0; i < n; i++) { 92 pw[1 << i] = i; 93 } 94 for(int i = 1; i <= n; i++) { 95 a[i] = ::a[i].to_double(); 96 } 97 DFS(1); 98 99 output(ans);100 101 /*for(int i = 1; i <= k + 1; i++) {102 out(Ans[i]); printf(" ");103 }104 puts("");*/105 return;106 }107 }108 109 int main() {110 111 //freopen("in.in", "r", stdin);112 113 scanf("%d%d%d", &n, &k, &p);114 for(int i = 1, x; i <= n; i++) {115 scanf("%d", &x);116 a[i] = x;117 }118 119 std::sort(a + 2, a + n + 1);120 if(n == 1) {121 output(a[1]);122 return 0;123 }124 if(n == 2) {125 if(a[1] > a[2]) {126 output(a[1]);127 }128 else {129 a[1] = (a[1] + a[2]) / 2;130 output(a[1]);131 }132 return 0;133 }134 if(a[1] >= a[n]) {135 output(a[1]);136 return 0;137 }138 if(k == 1) {139 Decimal tot = a[1], ans = a[1];140 int cnt = 1;141 for(int i = n; i >= 2; i--) {142 cnt++;143 tot += a[i];144 ans = std::max(ans, tot / cnt);145 }146 output(ans);147 return 0;148 }149 if(k >= n - 1) {150 for(int i = 2; i <= n; i++) {151 if(a[1] > a[i]) continue;152 a[1] = (a[1] + a[i]) / 2;153 }154 output(a[1]);155 return 0;156 }157 if(n <= 10) {158 bf::solve();159 return 0;160 }161 else {162 Decimal tot = a[1], ans = a[1];163 int cnt = 1;164 for(int i = n - k + 1; i >= 2; i--) {165 cnt++;166 tot += a[i];167 ans = std::max(ans, tot / cnt);168 }169 a[1] = ans;170 for(int i = n - k + 2; i <= n; i++) {171 if(a[1] > a[i]) continue;172 a[1] = (a[1] + a[i]) / 2;173 }174 output(a[1]);175 return 0;176 }177 return 0;178 }
正确的规律：最优策略一定是把一个后缀分成连续若干段。
于是以此DP，设f[i][j]表示前i次操作取到了j，此时1号点的最大值。转移就枚举从哪来即可。注意初始化。
1 #include2 3 // ---------- decimal lib start ---------- 4 5 const int PREC = 120; 6 7 // ---------- decimal lib end ---------- 8 9 const int N = 8010; 10 11 int n, k, p; 12 Decimal a[N]; 13 14 inline void output(Decimal x) { 15 std::cout << x.to_string(p + 5) << std::endl; 16 return; 17 } 18 19 inline void output(double x) { 20 printf("%.10f\n", x); 21 return; 22 } 23 24 inline void out(int x) { 25 for(int i = 0; i < n; i++) { 26 printf("%d", (x >> i) & 1); 27 } 28 return; 29 } 30 31 namespace bf { 32 33 const double eps = 1e-12; 34 35 double ans = 0, a[N], temp[101][101]; 36 int lm, pw[110101], Ans[N], now[N]; 37 38 void DFS(int x) { 39 /// check 40 double large(0); 41 for(int i = 1; i <= n; i++) { 42 if(large < a[i]) large = a[i]; 43 } 44 if(large < ans + eps) { 45 return; 46 } 47 if(fabs(large - a[1]) < eps || x > k) { 48 if(ans < a[1]) { 49 ans = a[1]; 50 memcpy(Ans + 1, now + 1, x * sizeof(int)); 51 } 52 return; 53 } 54 55 for(int i = 1; i <= n; i++) { 56 temp[x - 1][i] = a[i]; 57 } 58 for(int s = lm - 1; s > 1; s--) { 59 if(!(s - (s & (-s)))) continue; 60 double tot = 0; 61 int cnt = 0; 62 int t = s; 63 while(t) { 64 int tt = pw[t & (-t)] + 1; 65 tot += a[tt]; 66 cnt++; 67 t ^= 1 << (tt - 1); 68 } 69 tot /= cnt; 70 t = s; 71 while(t) { 72 int tt = pw[t & (-t)] + 1; 73 a[tt] = tot; 74 t ^= 1 << (tt - 1); 75 } 76 now[x] = s; 77 DFS(x + 1); 78 t = s; 79 while(t) { 80 int tt = pw[t & (-t)] + 1; 81 a[tt] = temp[x - 1][tt]; 82 t ^= 1 << (tt - 1); 83 } 84 } 85 now[x] = 0; 86 return; 87 } 88 89 inline void solve() { 90 91 /// DFS 92 lm = 1 << n; 93 for(int i = 0; i < n; i++) { 94 pw[1 << i] = i; 95 } 96 for(int i = 1; i <= n; i++) { 97 a[i] = ::a[i].to_double(); 98 } 99 DFS(1);100 101 output(ans);102 103 /*for(int i = 1; i <= k + 1; i++) {104 out(Ans[i]); printf(" ");105 }106 puts("");*/107 return;108 }109 }110 111 Decimal f[105][105];112 int sum[N];113 114 inline void solve() {115 int I = 2;116 while(a[1] > a[I]) ++I;117 for(int i = 1; i <= n; i++) {118 f[0][i] = a[1];119 }120 for(int i = 1; i <= k; i++) {121 f[i][I - 1] = a[1];122 for(int j = I; j <= n; j++) {123 /// f[i][j]124 f[i][j] = f[i - 1][j];125 for(int p = I - 1; p < j; p++) {126 Decimal t = (f[i - 1][p] + sum[j] - sum[p]) / (j - p + 1);127 if(f[i][j] < t) {128 f[i][j] = t;129 }130 }131 //printf("i = %d j = %d f = ", i, j); output(f[i][j]);132 }133 }134 output(f[k][n]);135 return;136 }137 138 int main() {139 140 //freopen("in.in", "r", stdin);141 //printf("%d \n", (sizeof(f)) / 1048576);142 143 scanf("%d%d%d", &n, &k, &p);144 for(int i = 1, x; i <= n; i++) {145 scanf("%d", &x);146 a[i] = x;147 }148 149 std::sort(a + 2, a + n + 1);150 for(int i = 1; i <= n; i++) {151 sum[i] = sum[i - 1] + (int)(a[i].to_double() + 0.5);152 }153 if(n == 1) {154 output(a[1]);155 return 0;156 }157 if(n == 2) {158 if(a[1] > a[2]) {159 output(a[1]);160 }161 else {162 a[1] = (a[1] + a[2]) / 2;163 output(a[1]);164 }165 return 0;166 }167 if(a[1] >= a[n]) {168 output(a[1]);169 return 0;170 }171 if(k == 1) {172 Decimal tot = a[1], ans = a[1];173 int cnt = 1;174 for(int i = n; i >= 2; i--) {175 cnt++;176 tot += a[i];177 ans = std::max(ans, tot / cnt);178 }179 output(ans);180 return 0;181 }182 if(k >= n - 1) {183 for(int i = 2; i <= n; i++) {184 if(a[1] > a[i]) continue;185 a[1] = (a[1] + a[i]) / 2;186 }187 output(a[1]);188 return 0;189 }190 if(n <= 4) {191 bf::solve();192 return 0;193 }194 else {195 solve();196 return 0;197 }198 return 0;199 }
考虑如何优化这个DP。