咳咳。。昨天前天纠结了十几个小时的难题。。。。我估计此题我短时间类还不能做到不TLE。。。
特寻觅此作品研读用。。
我简单叙述一下题意，0/1背包基础上，每个物品属于一集合，要求不同集合中的物品至少被选中一次。。。
题目在这边 HOJ 2839. I love sneakers! … 。
#include
using namespace std;
struct point{
int tp,pri,val;
}a[150];
int n,m,k,dp[15][21000];
bool cmp(point p1, point p2){
return(p1.tp-p2.tp<0);
}
int main()
{
int i,kk,tmp,pre,tot;
while(scanf("%d %d %d",&n,&m,&k)==3){
for(i=1;i<=n;i++)
{
scanf("%d %d %d",&a[i].tp,&a[i].pri,&a[i].val);
}
memset(dp,0,sizeof(dp));
sort(a+1,a+n+1,cmp);
a[0].tp=0; tot=0;
for(kk=1;kk<=n;kk++){
if(a[kk].tp!=a[kk-1].tp)
{
tot++;
for(i=0;i<=m;i++) dp[tot][i]=-1;
}
for(i=m;i>=0;i--)
if((i>=a[kk].pri))
{
if(dp[tot][i-a[kk].pri]!=-1)
dp[tot][i]=max(dp[tot][i-a[kk].pri]+a[kk].val,dp[tot][i]);
if(dp[tot-1][i-a[kk].pri]!=-1)
dp[tot][i]=max(dp[tot][i],dp[tot-1][i-a[kk].pri]+a[kk].val);
}else break;
}
if(dp[tot][m]!=-1&&tot==k)printf("%d\n",dp[tot][m]);
else printf("Impossible\n");
}
return 0;
}
