当前位置:网站首页>HDU7033 Typing Contest

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.
 
 
 
 

版权声明
本文为[mrclr]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210808003020579r.html

随机推荐