学步园

You've got a positive integer sequence a₁, a₂, ..., a_n. All numbers in the sequence are distinct.
Let's fix the set of variables b₁, b₂, ..., b_m. Initially each variable
b_i
(1 ≤ i ≤ m) contains the value of zero. Consider the following sequence, consisting of
n operations.

有n个数, 作为一组等式的得数.

有m个变量, 可以视为容器.

The first operation is assigning the value of a₁ to some variable
b_x
(1 ≤ x ≤ m). Each of the following
n - 1 operations is assigning to some variable
b_y the value that is equal to the sum of values that are stored in the variables
b_i and
b_j
(1 ≤ i, j, y ≤ m). At that, the value that is assigned on the
t-th operation, must equal
a_t. For each operation numbers
y, i, j are chosen anew.

第一个变量首先赋值为a₁, 接下来给其他的变量赋值(其他的变量可以是已经出现过的, 将覆盖原值), 并且需要满足第t个赋值语句的返回值与a_t.相等.

Your task is to find the minimum number of variables m, such that those variables can help you perform the described sequence of operations.

问题是找出最小的m. 即容器个数.

思路:

用样例模拟了一下, 前几个还好判断, 到后面就需要看看再往后是否需要用到这个数来决定是否覆盖...有点像背包问题, 要合理地调度前面的变量...以免出现误删. 同时又要保证总的变量数最少.

用dp.

dp记录当前状态下需要的最少变量数...

看题解:

http://blog.sina.com.cn/s/blog_6ffc3bde01017l92.html

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 25
int n,a[25],dp[1<<23];
//m表示状态一共23位. 从右往左数. 哪一位为1则表示至少需要多少个中继.
int fun(int m,int x) //扫描到第x位至少需要多少个中继(x从0开始)
{
    if(dp[m]) return dp[m];
    int c = __builtin_popcount(m),v = 0,mn = INF;//c下一状态需要我保证的中继的个数
    for(int i = 0; i < x; i ++)
    {
        for(int j = 0; j <= i; j ++)
        {
            if(a[i] + a[j] == a[x])//如果这两个结果相加可以得到最终结果(尽可能靠前),则...
            {//应该观察到, 每一个a[i]都对应一个变量b,因为结果要有容器.
            //每一个现存的容器都对应了一个a[i].容器是游离的,未知的,只当需要的时候将它计算进来. 每一步都如此, 就可以保证正确.
                v = fun((m&~(1<<x))|(1<<(x-1))|(1<<i)|(1<<j), x-1);
                //第一项表示消除当前变量;1<<(x-1)表示扫描到了前一位,那么这前一位必然要占一个变量.
                //后两项就表示额外需要保留的中介项.(就这么简单?)
                mn = min(mn,max(v,c));//其实所有的数字都是由c得到的，v只作为中介，将不同的c作比较
            }
        }
    }
    return dp[m] = mn;
}
int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i ++)
        scanf("%d",&a[i]);
    dp[1] = 1;//初始条件为扫描到第一位..必然至少需要1个变量
    int ans = fun(1<<(n-1),n-1);
    if(ans == 25) ans = -1;
    printf("%d\n",ans);
    return 0;
}

感觉仍是非常难以理解啊......

主要是要培养另一种分析问题的角度.

在本题中,则是:

抓住核心:

每一个得数由两个加数组成, 这两个加数都是之前的某个得数.

如果就选择这两个得数作为加数, 那么这两个得数对应的容器就要保留下来作为中转,而不能被覆盖(复用).

而当前的这个得数需要使用的容器又可以由更靠后的需求决定...

对!还有一点!!容器的编号是不需要考虑的,只要记录所需容器的最大个数,那么就一定够用啦.

m就是有用容器的保留...扫描到不同位时m的变化可看做变量的申请与释放!

本题值得回味啊....

附popcount的一种二分实现...

unsigned popcount (unsigned u)
{
    u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
    u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
    u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
    u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
    u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
    return u;
}

略神呐><