首页 > ACM题库 > HDU-杭电 > HDU 3364-Lanterns-背包问题-[解题报告]HOJ
2014
03-16

HDU 3364-Lanterns-背包问题-[解题报告]HOJ

Lanterns

问题描述 :

Alice has received a beautiful present from Bob. The present contains n lanterns and m switches. Each switch controls some lanterns and pushing the switch will change the state of all lanterns it controls from off to on or from on to off. A lantern may be controlled by many switches. At the beginning, all the lanterns are off.

Alice wants to change the state of the lanterns to some specific configurations and she knows that pushing a switch more than once is pointless. Help Alice to find out the number of ways she can achieve the goal. Two ways are different if and only if the sets (including the empty set) of the switches been pushed are different.

输入:

The first line contains an integer T (T<=5) indicating the number of test cases.
The first line of each test case contains an integer n (1<=n<=50) and m (1<=m<=50).
Then m lines follow. Each line contains an integer k (k<=n) indicating the number of lanterns this switch controls.
Then k integers follow between 1 and n inclusive indicating the lantern controlled by this switch.
The next line contains an integer Q (1<=Q<=1000) represent the number of queries of this test case.
Q lines follows. Each line contains n integers and the i-th integer indicating that the state (1 for on and 0 for off) of the i-th lantern of this query.

输出:

The first line contains an integer T (T<=5) indicating the number of test cases.
The first line of each test case contains an integer n (1<=n<=50) and m (1<=m<=50).
Then m lines follow. Each line contains an integer k (k<=n) indicating the number of lanterns this switch controls.
Then k integers follow between 1 and n inclusive indicating the lantern controlled by this switch.
The next line contains an integer Q (1<=Q<=1000) represent the number of queries of this test case.
Q lines follows. Each line contains n integers and the i-th integer indicating that the state (1 for on and 0 for off) of the i-th lantern of this query.

样例输入:

2
3 2
2 1 2
2 1 3
2
0 1 1
1 1 1
3 3
0
0
0
2
0 0 0
1 0 0

样例输出:

Case 1:
1
0
Case 2:
8
0

某种排序下的01背包,直接01背包肯定是错的,因为题目加了一些限制,需按q-p 从小到大将物品排序,至于为什么还是不清楚

LanternsView Code

#include<iostream>
#include<algorithm>
using namespace std;
int dp[5005];
struct good
{
    int p,q,v;
}g[505];
bool cmp(good a,good b)
{
    return a.q-a.p<b.q-b.p;
}
int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)==2)
    {
        for(int i=0;i<n;i++)
            scanf("%d %d %d",&g[i].p,&g[i].q,&g[i].v);
        sort(g,g+n,cmp);
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            for(int j=m;j>=0;j--)
            {
                if(j<g[i].q || j-g[i].p<0)
                    continue;
                dp[j]=max(dp[j],dp[j-g[i].p]+g[i].v);
            }
        }
        int ans=0;
        for(int i=0;i<=m;i++)
            if(dp[i]>ans)
                ans=dp[i];
        printf("%d\n",ans);
    }
    return 0;
}

 

参考:http://www.cnblogs.com/nanke/archive/2012/02/12/2347621.html


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c