HDU7033 Typing Contest

2021-08-08 00:31:13 mrclr

Portal

I thought about this question for a while , Feeling is dp, But the thinking is still not deep .

The last reduction of the enumeration range is really powerful , It's hard for me to think of it .

First of all, the beautiful thing about the solution is to $$f_i$$ expand $$100$$ times , You can avoid the operation of floating-point numbers .

Suppose we choose a size of $$k$$ Set $$S=\{ t_1,t_2,\cdots,t_k \}$$, So the first $$i$$ Personal typing speed is $$\frac1{10000}s_{t_i}(10000 - \sum\limits_{j=1}^{k}f_{t_i} * f_{t_j} + f_{t_i} * f_{t_i})=\frac1{10000}s_{t_i}[10000 - f_{t_i}(\sum\limits_{j=1}^{k}f_{t_j} - f_{t_i})]$$.

（ The following is for convenience , Ignoring the previous $$\frac1{10000}$$）

If $$F=\sum_{i \in S}f_{t_i}$$ A certain , Then everyone's typing speed will be certain . enumeration $$F$$, It becomes a 01 knapsack ： For total capacity $$F$$, The weight of each person is $$f_i$$, The value is $$s_{t_i}[10000 - f_{t_i}(F - f_{t_i})]$$.

But such time complexity is too high , So the question explains ,$$F$$ Don't enumerate a lot , Only for $$100\sqrt{n+2}$$ that will do , So the time complexity is $$O(5000n^2)$$ Of course. . Next, we give a wonderful proof ：

among $$\frac{\sum_{i=1}^k f_i^3}{\sum_{i=1}^k f_i} \leqslant 10000$$ The zoom in and zoom out of this step uses $$\textrm{min} \{\frac{a}{b},\frac{c}{d} \} \leqslant \frac{a+c}{b+d} \leqslant \textrm{max} \{ \frac{a}{b}, \frac{c}{d}\}$$.

Mathematically speaking , The derivation process is not difficult , But I really didn't think in this direction , Long knowledge .

In addition, in the code , For the first time, it was hit by a floating-point error pit . multiply $$100$$ Taking the integer part again really can't (int)(x*100) That's how it's written , Take it if you don't believe it x=0.57 try , He will keep it for you as 56.9999999. And output , Although in theory only 4 Decimal place , But just divide by 10000 There was a mistake, too , do not know why .

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 105;
const int maxd = 1.5e3 + 5;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen("1009.in", "r", stdin);
freopen("ha.out", "w", stdout);
#endif
}

char ff[5];
int n, f[maxn];
ll s[maxn];

ll dp[maxd];
In void solve()
{
int sum = 0;
for(int i = 1; i <= n; ++i) sum += f[i];
while(sum * sum >= 10000 * (2 + n)) sum--;
ll ans = 0;
for(int F = 0; F <= sum; ++F)
{
fill(dp, dp + F + 1, 0);
for(int i = 1; i <= n; ++i)
{
ll val = s[i] * (10000 - f[i] * (F - f[i]));
if(val <= 0 || f[i] > F) continue;
for(int j = F; j >= f[i]; --j) dp[j] = max(dp[j], dp[j - f[i]] + val);
}
ans = max(ans, dp[F]);
}

string ret = to_string(ans);
while (ret.size() < 5) ret = "0" + ret;
ret = ret.substr(0, ret.size() - 4) + "." + ret.substr(ret.size() - 4, 4);
ret += "00000";
cout << ret << endl;
}

int main()
{
// MYFILE();
int T = read();
while(T--)
{
n = read();
for(int i = 1; i <= n; ++i)
{
s[i] = read(); scanf("%s", ff);
f[i] = (ff[0] - '0') * 100 + (ff[2] - '0') * 10 + ff[3] - '0';
}
solve();
}
return 0;
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.


https://chowdera.com/2021/08/20210808003020579r.html