T1（数学化审题）
541。
观察到其实和最初功率没有关系，功率就是个系数，于是可以把
系数提出来。于是定义f[i]为功率为1，i~n最长信息。
直接转移就好。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, k, c, w;
double f[N];
int a[N], b[N];
int main()
{
freopen("broadcast.in", "r", stdin);
freopen("broadcast.out", "w", stdout);
scanf("%d%d%d%d", &n, &k, &c, &w);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &a[i], &b[i]);
for (int i = n; i; i -- )
{
f[i] = f[i + 1];
if (a[i] == 1) f[i] = max(f[i], b[i] + ((double)1 - 0.01 * k) * f[i + 1]);
else f[i] = max(f[i], ((double)1 + 0.01 * c) * f[i + 1] - b[i]);
}
printf("%.2lf\n", w * f[1]);
fclose(stdin);
fclose(stdout);
return 0;
}
T2(线性组合，同余处理，变量枚举，数据反推）
257。
这里首先考虑枚举啊。只要枚举my,就可以一块计算，但是这样有重复，啥时候重复呢？
注意到，n的范围很小，可能往n去考虑。这里发现my%n一致的话，可以一块算啊，大的my没有用，在算x的情况算到了。于是处理dp[i]。
这样答案就累加(q - f[i]) / n + 1。+1是x=0的情况。思想上，多个量考虑枚举，范围反推想法。可以考虑同余。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
LL dp[N];
LL n, m, k;
int main()
{
scanf("%lld%lld%lld", &n, &m, &k);
for (int i = m % n, last = 0; i != 0 && dp[last] < k && !dp[i]; i = (i + m) % n)
{
dp[i] = dp[last] + m;
last = i;
}
LL ans = k / n; //提前处理%n=0
for (int i = 0; i < n; i ++ )
if (dp[i] && dp[i] <= k)
ans += (k - dp[i]) / n + 1;
cout << k - ans << endl;
return 0;
}
T3(方差，变量枚举）
先把方差化成好算的形式：
这样发现俩变量，处理不了。于是就把他作为一维状态。
二元组，枚举一个
dp维护平方和，easy。
一开始写挂的原因是平方和应该最小。取成max了。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 40, M = 2010;
int f[N][N][M];
int n, m;
int sum;
int w[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
scanf("%d", &w[i][j]);
sum = max(sum, w[i][j]);
}
memset(f, 0x3f, sizeof f);
f[0][1][0] = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
for (int k = 0; k <= sum * (i + j - 1); k ++ )
{
f[i][j][k] = min(f[i - 1][j][k - w[i][j]], f[i][j - 1][k - w[i][j]]) + w[i][j] * w[i][j];
}
int res = 0x3f3f3f3f;
for (int k = 0; k <= sum * (n + m - 1); k ++ )
if (f[n][m][k] < 1e9) res = min(res, (n + m - 1) * f[n][m][k] - k * k);
printf("%d\n", res);
return 0;
}
T4（分层图，dp，搜索及其联系）
多变量，想到设0/1状态。
这个转移方程有环，处理不了。但是，我们可以升维破坏，就是按照最短长度取转移（其实就是答案，神奇吧），这其实就是搜索！！!，这就是在做最短路，bfs了。
从图论角度，我们把每个点拆成了两个点，只不过这个转移方程有环，那我们求的其实就是最短路，这跑bfs就行。这其实就是分层图。