BZOJ 3450: Tyvj1952 Easy

对于连续的一段o
考虑第i个o
贡献的权值是2i-1
这样Σvi=n^2(1<= i <= n) 对所有n都有效 f[i]表示考虑前i个按键 期望收益是多少 问题是怎么转移呢0.0 显然f[i] = f[i - 1] + (i的期望收益) (根据期望可加) i的期望收益 枚举所有?的选择 设第j种选择最后有连续len[j]个o 一共m种选择 则i的期望收益为: ----------------------------- Σ(len[j] * 2 - 1) / m = (Σ(len[j]) / m) * 2 - 1 ----------------------------- Σ(len[j]) / m其实考虑前i位 最后连续的o的期望长度 这样就很简单了 g[i]表示前i为最后连续o的期望长度 然后就可以推了 但是如果长度为0 则按那个公式期望收益为0*2-1 = -1 显然是错的 要特判掉 怎么弄呢= = 可以从g[i - 1]转移 如果s[i] == 'x'就不管了 f[i] = f[i - 1] 如果s[i] == 'o'也不会有0的情况 直接转移即可 f[i] = f[i - 1] + g[i] * 2 - 1 如果s[i] == '?'那么有1/2的概率会长度为0则 f[i] = f[i - 1] + (g[i - 1] * 2 + 1) / 2即可(有1/2概率没收益)

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const int maxn = 300005;
 
ld f[maxn], g[maxn];
int n;
 
int main()
{
    scanf("%d\n", &n);
    for (int i = 1; i <= n; ++i)
    {
        char c = getchar();
        if (c == 'x') f[i] = f[i - 1], g[i] = 0;
        if (c == 'o') g[i] =  g[i - 1] + 1, f[i] = f[i - 1] + g[i - 1] * 2 + 1;
        if (c == '?') g[i] = (g[i - 1] + 1) / 2, f[i] = f[i - 1] + g[i - 1] + 0.5;
    }
    printf("%.4f", (double)f[n]);
}

BZOJ 3437: 小P的牧场

这题一看就是奇怪的dp啊╮(╯_╰)╭
f[i]表示考虑前i个牧场 且第i个有取的最小代价
但是把这个方程列出来 会发现这个方程有一部分的系数是一个公差为1的等差数列
这就很蛋疼
不能以一个项数为O(1)级的多项式表示i取j决策的代价

怎么办呢
所谓正难则反
首先设答案为类似只在n+1号位置取一个观察站 的代价
如果这时候在i位置取一个观察站 则答案会减少(sum[i] * (n – i) – a[i])
f[i]表示考虑i~n的牧场 最多可以扣掉多少代价 且i有取
方程为
f[i] = max(a[i] + f[j] + sum[i] * (j – i))
sum[i]表示Σ(b[j])(1 <= j <= i) 这个方程拿去斜率优化一下即可 另外这个系列的数据范围巨坑无比 n的范围是100w 他写变成n <= 1000000,0 后面加了个,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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const ll maxn = 1000 * 1000 + 5;
 
struct poll
{
    ll x, y;
    poll(ll a = 0, ll b = 0) : x(a), y(b) {}
};
 
poll q[maxn];
ll f[maxn], n, a[maxn], b[maxn], sum[maxn], h, t;
ll ans;
 
ll xj(poll a, poll b, poll c)
{
    return ((ll)b.x - a.x) * (c.y - a.y) - ((ll)b.y - a.y) * (c.x - a.x);
}
 
ll calc(ll i, poll j)
{
    return -a[i] + j.y + sum[i] * (j.x - i);
}
 
int main()
{
    scanf("%lld", &n);
    for (ll i = 0; i < n; ++i)
        scanf("%lld", &a[i]);
    for (ll i = 0; i < n; ++i)
    {
        scanf("%lld", &b[i]);
        ans += ((ll)n - i) * b[i];
        if (!i) sum[i] = b[i];
        else sum[i] = sum[i - 1] + b[i];
    }
    f[n - 1] = sum[n - 1] - a[n - 1];
    h = t = 0;
    q[0] = poll(n - 1, f[n - 1]);
    ll as = f[n - 1];
    for (ll i = n - 2; i >= 0; --i)
    {
        while (h < t && calc(i, q[h]) <= calc(i, q[h + 1])) ++h;
        f[i] = calc(i, q[h]);
        while (h < t && xj(q[t - 1], q[t], poll(i, f[i])) <= 0) --t;
        q[++t] = poll(i, f[i]);
        as = max(as, f[i]);
    }
    printf("%lld", ans - as);
}

【World Finals】2010 J

【试题编号】
2010 J
【名称】
Sharing Chocolate
【题目大意】
给n*m的方格 每次可以沿平行x或y切一刀 问最后能不能分成指定的一些面积
【算法讨论】
f[i][j] 表示长为i的方格 j值状压变量 表示这里面有哪些面积 对应的宽可以求出来
每次枚举一个切的方法 然后枚举j的切分 进行更新 用记忆话比较好做
【时空复杂度】
O(n^2 * 2^k * 2^k)
O(n*2^k)
【code】

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
int n, x, y, a[20], sum[40000];
bool f[105][40000], b[105][40000];
int lowbit(int a)
{
    return a & (-a);
}
bool dfs(int x, int y, int t)
{
    if (b[x][t]) return f[x][t];
    if (!(t - lowbit(t)))
        return b[x][t] = f[x][t] = true;
    bool br = false;
    for (int i = 1; i < x; ++i)
    {
        if (br) break;
        for (int j = (t - 1) & t; j; j = (j - 1) & t)
            if (i * y == sum[j] && (x - i) * y == sum[t ^ j] && dfs(i, y, j) && dfs(x - i, y, t ^ j))
            {
                br = true;
                break;
            }
    }
    for (int i = 1; i < y; ++i)
    {
        if (br) break;
        for (int j = (t - 1) & t; j; j = (j - 1) & t)
            if (x * i == sum[j] && x * (y - i) == sum[t ^ j] && dfs(x, i, j) && dfs(x, y - i, t ^ j))
            {
                br = true;
                break;
            }
    }
    b[x][t] = true;
    return f[x][t] = br;
}
int main()
{
    int test = 0;
    while (scanf("%d", &n) && n)
    {
        scanf("%d%d", &x, &y);
        memset(f, 0, sizeof(f));
        memset(b, 0, sizeof(b));
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        for (int i = 0; i < (1 << n); ++i)
            for (int j = 0; j < n; ++j)
                if (i & (1 << j))
                    sum[i] += a[j];
        printf((dfs(x, y, (1 << n) - 1) ? "Case %d: Yes\n" : "Case %d: No\n"), ++test);
    }
}

【World Finals】2008 F

【试题编号】
2008 F
【名称】
Glenbow Museum
【题目大意】
让你画一个n个点的多边形 度数为90或270 要在多边形内存在一个点 可以观测到所有点 问方案数
【算法讨论】
显然 不能出现连续的C 而且最后R的个数-C的个数为4 求方案数
f[i][j][k]表示前i个点 有j个C 最后一个k的方案数 注意首位要特殊处理
【时空复杂度】
O(n^2)
O(n^2)
【code】

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;

int n;
ll f[1005][1005][2], g[1005][1005][2];

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    g[1][0][0] = 1;
    f[1][1][1] = 1;
    for (int i = 1; i < 1000; ++i)
        for (int j = 0; j <= i; ++j)
            for (int k = 0; k < 2; ++k)
            {
                f[i + 1][j][0] += f[i][j][k];
                if (!k)
                    f[i + 1][j + 1][1] += f[i][j][k];

                g[i + 1][j][0] += g[i][j][k];
                if (!k)
                    g[i + 1][j + 1][1] += g[i][j][k];
            }
    int test = 0;
    while   (scanf("%d", &n) && n)
    {
        ++test;
        if (n < 4 || (n & 1))
            printf("Case %d: %d\n", test, 0);
        else
            printf("Case %d: %I64d\n", test, f[n][(n - 4) / 2][0] + g[n][(n - 4) / 2][0] + g[n][(n - 4) / 2][1]);
    }
    fclose(stdin);fclose(stdout);
}

【World Finals】1999 E

【试题编号】
1999 E
【名称】
Trade on Verweggistan
【题目大意】
有m个工厂 每个工厂有好几箱东西 每箱东西都有独立的价格 用10减价格就是收益 每次只能买前几箱 问最大收益 和需要的箱数
【算法讨论】
算出10-价格的前缀和数组 最大的数如果是正的 就是这个工厂的贡献 全部加起来就是ans 对于一个工厂 有几个跟最大前缀和一样的前缀和就是合法的个数 把每个工厂的可行个数分别有哪些算出来后 用类似背包的做法去算箱数即可
【时空复杂度】
O(n^2*b^2)
O(n^2*m)
【code】

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
int n, f[52][1005], mx[52], num[52], sum[52][25];
int main()
{
    int test = 0;
    while (scanf("%d", &n) && n)
    {
        ++test;
        memset(f, 0, sizeof(f));
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < 52; ++i)
            mx[i] = -0x3f3f3f3f;
        int ans = 0;
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", &num[i]);
            for (int j = 0; j < num[i]; ++j)
            {
                scanf("%d", &sum[i][j]);
                sum[i][j] = 10 - sum[i][j];
                if (j) sum[i][j] += sum[i][j - 1];
                mx[i] = max(mx[i], sum[i][j]);
            }
            if (mx[i] >= 0) ans += mx[i];
        }
        printf("Workyards %d\nMaximum profit is %d.\nNumber of pruls to buy:", test, ans);
        if (mx[0] < 0) f[0][0] = true;
        else
        {
            for (int i = 0; i < num[0]; ++i)
                if (sum[0][i] == mx[0])
                    f[0][i + 1] = true;
            if (mx[0] == 0) f[0][0] = true;
        }
        for (int i = 1; i < n; ++i)
        {
            if (mx[i] <= 0)
                for (int j = 0; j <= n * 20; ++j)
                    f[i][j] = f[i - 1][j];
            if (mx[i] >= 0)
                for (int j = 0; j <= n * 20; ++j)
                    if (f[i - 1][j])
                        for (int k = 0; k < num[i]; ++k)
                            if (sum[i][k] == mx[i])
                                f[i][j + k + 1] = true;
        }
        int tot = 0;
        for (int i = 0; i <= 1000; ++i)
            if (f[n - 1][i])
            {
                ++tot;
                printf(" %d", i);
                if (tot == 10) break;
            }
        printf("\n");
    }
}

【World Finals】2013 H

【试题编号】
2013 H
【名称】
Матрёшка
【题目大意】
给一堆数 最后要合成很多1~k的数 每次只能合成相邻的 问合成最小代价
【算法讨论】
算出g[i][j]表示把 i~j合并成一个需要的最小代价
如果i~j有重复的数 就0x7fffffffffffffff
主要问题是把相邻两个区间合并的代价
代价就是总长度-某个区间最小的连续的有几个数
设最小的数的位置为p 枚举点为k
如果k

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;

int g[505][505], f[505][505], n, m, v[505], b[1000005], to[505], tot, mi[505][505], sum[505][505];

bool cmp(int a, int b) { return v[a] < v[b]; }

bool check(int l, int r)
{
    for (int i = l; i <= r; ++i)
        if (v[i] > r - l + 1) return false;
    return true;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &v[i]);
    memset(g, 0x3f, sizeof(g));
    memset(mi, 0x3f, sizeof(mi));
    for (int i = 0; i < n; ++i)
        for (int j = i; j < n; ++j)
            if (i == j) mi[i][j] = v[i];
            else mi[i][j] = min(mi[i][j - 1], v[j]);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= n; ++j)
            sum[i][j] = ((i == 0) ? (v[i] == j ? 1 : 0) : (sum[i - 1][j] + (v[i] == j ? 1 : 0)));
    for (int i = 0; i < n; ++i)
        for (int j = 1; j <= n; ++j)
            sum[i][j] += sum[i][j - 1];
    for (int i = n - 1; i >= 0; --i)
        for (int j = i; j < n; ++j)
        {
            if (i == j)
            {
                g[i][j] = 0;
                continue;
            }
            ++tot;
            bool br = true;
            int p = 0, MI = i;
            for (int k = i; k <= j; ++k)
                if (b[v[k]] == tot)
                {
                    br = false;
                    break;
                }
                else
                {
                    b[v[k]] = tot;
                    if (v[k] < v[MI]) MI = k;
                    ++p;
                }
            if (!br) continue;

            for (int k = MI; k > i; --k)
                g[i][j] = min(g[i][j], g[i][k - 1] + g[k][j] + p - (sum[j][mi[i][k - 1]] - sum[k - 1][mi[i][k - 1]]));

            for (int k = MI; k < j; ++k)
                g[i][j] = min(g[i][j], g[i][k] + g[k + 1][j] + p - (sum[k][mi[k + 1][j]] - (i ? sum[i - 1][mi[k + 1][j]] : 0)));
        }
    memset(f, 0x3f, sizeof(f));
    for (int i = n - 1; i >= 0; --i)
        for (int j = i; j < n; ++j)
        {
            if (check(i, j)) f[i][j] = g[i][j];
            for (int k = i; k < j; ++k)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
        }
    if (f[0][n - 1] >= 0x3f3f3f3f) printf("Impossible");
    else printf("%d", f[0][n - 1]);
    fclose(stdin);fclose(stdout);
}