分类目录归档:DP

[UVa10859 – Placing Lampposts]DP状态表示的转换。

该题给出N个点M条边的无向无环图,在尽量少的节点上放灯,使得所有边都被照亮,每个节点将照亮与它相连的边。在放灯数量最少的前提下要求被两盏灯同时照亮的的边数应尽量大。

该题难点在于如何同时做到放灯最少和被两栈等同时照亮的最大。

首先统一到 “求最小” 的问题中来,问题转化为:在放灯数x最少的情况下使得仅被一条个等照亮的边数c最小。

定义一个较大的数M,使其超过题目情况中 c 的和的上界,该题可定义为2000.

则把状态转换为使得 M * x + c 最小。

那么最后放灯数应该是 ans / M, 仅被一个灯照亮的边数为: ans % M

还是忍不住贴个代码。。

# include <cstdio>
# include <cstring>
# include <algorithm>
# define rep(i, n) for (int i = 0; i < n; ++i )
using namespace std;

const int M = 2000;
int n, m;

struct edge
{
    int v, next;
}e[2009];

int h[1003], tot;

void add(int a, int b)
{
    e[++tot].v = b;
    e[tot].next = h[a];
    h[a] = tot;
}

bool v[2003];
int f[2003][2];

void dfs(int x, int fa)
{
    int j;
    v[x] = true;
    f[x][0] = 0;
    f[x][1] = M;
    for (int i = h[x]; i; i = e[i].next)
    {
        j = e[i].v;
        if ( !v[j] ) dfs(j, x);
        if ( j == fa ) continue;
        f[x][1] += min(f[j][0] + 1, f[j][1]);
        f[x][0] += f[j][1] + 1;
    }
}

int main()
{
    int t, a, b;
    scanf("%d", &t);
    while ( t-- )
    {
        memset(h, 0, sizeof h);
        memset(v, false, sizeof v);
        tot = 0;
        scanf("%d%d", &n, &m);
        rep(i, m)
        {
            scanf("%d%d", &a, &b);
            add(a, b);
            add(b, a);
        }
        int ans = 0;
        rep(i, n)
            if ( !v[i] )
            {
                dfs(i, -1);
                ans += min(f[i][0], f[i][1]);
            }
        printf("%d %d %d\n", ans/M, m - ans % M, ans % M);
    }
    return 0;
}

二进制表示的集合 枚举子集 的快速方法。

令要 枚举子集 的集合为S ,每一个二进制位表示一个元素是否存在。

则可 for (int S0 = S; S0; S0 = (S0 – 1)&S )

证明:

(S0 – 1)&S必然是S的子集

因为是从最后一位开始减小,所以(S0 – 1)&S必然是最十进制数位上最靠近S0的S的自己。

故可以用(S0 – 1) & S 来生成下一个子集并得到所有S的子集。

POJ 1953 基础的DP递推思想

题意:求t个n位的2进制数中,有多少个没有连续的1.

dp0[x]表示以0开头长度为x的这类01串的个数,dp1[x]表示以1开头长度为x的这类01串的个数

dp0[x] = dp0[ x-1 ] + dp1[ x-1 ], dp0[1] = 1;

dp1[x] = dp0[ x-1 ] , dp1[1] = 1;

合并 dp0[x] + dp1[x] = dp0[x-1] + dp1[x-1] + dp0[x-1]
又dp0[x-1] = dp0[x-2] + dp1[x-2]
得:
ans[i] = ans[i-1] + ans[i-2]
由于第i位可任选0或1:
选1时,i-1位选0,i-2位选1的合法
选0时,i-1位选1,i-2位选0的合法
# include <iostream>
# include <algorithm>
using namespace std;

const int _ = 0;
long long ans[50] = {0};

int t, n;

int main()
{
    int i;
    ans[1] = 2LL, ans[2] = 3LL;
    for ( i = 3; i < 50; ++i ) ans[i] = ans[i-1] + ans[i-2];
    cin >> t;
    for ( i = 1; i <= t; ++i )
    {
        cin >> n;
        cout << "Scenario #" << i <<":" << endl;
        cout << ans[n] << endl << endl;
    }
    return 0>_<0;
}