夏娜的菠萝包 JDFZ1098

Description

问题描述:夏娜很喜欢吃菠萝包,她的经纪人RC每半个月就要为她安排接下来的菠萝包计划。今天是7月份,RC又要去商场进货买菠萝包了。这次RC总共买了N种菠萝包,每种一个。每个菠萝包都有一个初始美味值Ti,每过一天就会减少Di,即第2天美味值为Ti-Di,第3天为Ti-2*Di,依此类推。一旦美味值减为负数,那个包就坏掉了,不能吃了。 RC每天都要为夏娜安排当天吃菠萝包的组合,这些组合不是随意的,而是只能从夏娜喜欢的M种搭配中挑选一种。每种搭配是由Ki个菠萝包组成的,一种搭配的总美味值是这Ki个菠萝包当天的美味值之和再加上一个额外的搭配美味值Ei。不过要注意,一旦某种搭配的其中一个菠萝包坏掉了,这个搭配就不能选用了。而且,有可能存在两个搭配,里面的组合是一样的,但额外的搭配美味值却不同。 RC想让可爱的夏娜尽可能地吃得美味,因此希望能找出一种最优的方案,让小夏娜吃上若干天的菠萝包,这些天的美味值之和最大。但RC面临着两个邪恶的敌人,一个叫bug,一个叫zzy,他们也想抢夺这个经纪人之位,因此要是他们提出更优的方案,RC就可能会失去他的夏娜了。那么,你们能帮帮这个可怜的RC吗?

Input

输入格式:输入文件包含多组数据。每组数据的第一行为一个正整数N(N<=14),表示菠萝包的种数,按1-N编号。接下来N行,每行两个正整数Ti(Ti<100)和Di(Di<100),表示第i种菠萝包的初始美味值和每天递减值。第N+2行为一个正整数M,表示搭配的种数。接下来M(M<=20)行,每行先是一个正整数Ki,表示组成这个搭配的菠萝包数目,然后是一个非负整数Ei(Ei<100),表示这种搭配额外的美味值,最后是Ki个整数,每个整数为菠萝包的编号。当N=0时表示输入结束。

Output

输出格式:对于每组输入数据输出一行,仅包含一个整数,表示最大的美味值之和。

Sample Input

输入样例: 2 3 1 4 2 2 1 1 1 1 1 2 2 3 1 4 2 3 1 1 1 1 1 2 2 2 1 2 0

Sample Output

输出样例: 8 9
 
 
 
明显的状压dp
状态:f[j+1][S|gru[i].sta]=max(f[j][S]+gru[i].val-(j*gru[i].minu),f[j+1][S|gru[i].sta]);
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
#define N 1<<14
int f[][N];
int n,m;
int T[],D[],tim[];
struct node
{
int sta;
int val;
int tim1;
int minu;
}gru[];
void init()
{
memset(f,,sizeof(f));
memset(T,,sizeof(T));
memset(tim,,sizeof(tim));
memset(gru,,sizeof(gru));
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==)return ;
init();
for(int i=;i<=n;i++)
{
scanf("%d%d",&T[i],&D[i]);
tim[i]=T[i]/D[i];
}
scanf("%d",&m);
for(int i=;i<=m;i++)
{
int x;
gru[i].tim1=<<;
scanf("%d%d",&x,&gru[i].val);
for(int j=;j<=x;j++)
{
int y;
scanf("%d",&y);
gru[i].val+=T[y];
gru[i].minu+=D[y];
gru[i].tim1=min(gru[i].tim1,tim[y]);
gru[i].sta=(gru[i].sta|(<<(y-)));
}
}
int ans=;
for(int S=;S<(<<n);S++)
{
for(int i=;i<=m;i++)
{
if(gru[i].sta&S)continue;
for(int j=gru[i].tim1;j>=;j--)
{
f[j+][S|gru[i].sta]=max(f[j][S]+gru[i].val-(j*gru[i].minu),f[j+][S|gru[i].sta]);
ans=max(f[j+][S|gru[i].sta],ans);
}
}
}
printf("%d\n",ans);
}
return ;
}
上一篇:java.awt.swing菜单组件


下一篇:eNSP仿真学习,网络入门!