hdu4778 状态压缩
2024-08-24 04:34:50
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string.h>
using namespace std;
bool use[<<];
int dp[<<];
int G,B,S;
int P[][];
int nu[];
int work3()
{
int ans=;
for(int i=; i<=G; i++)
{
int ge=;
for(int j=;j <B; j++)
ge+=P[j][i];
ans+=ge/S;
}
return ans;
}
int jia(int j)
{
int ans=;
for(int i=; i<=G; i++)
{
nu[i]+=P[j][i];
ans+=nu[i]/S;
nu[i]%=S;
}
return ans;
}
void jian(int j)
{
for(int i=; i<=G; i++)
{
nu[i]=((nu[i]-P[j][i])%S+S)%S;
}
}
void dfs(int D,int cntge)
{
if(use[D])return ;
use[D]=true;
dp[D]=;
for(int j=;j<B; j++)
{
if((D&(<<j))==)continue;
int num=jia(j);
dfs(D^(<<j),cntge-num);
if(num>)
dp[D]=max(dp[D^(<<j)]+num,dp[D]);
else{
dp[D]=max(cntge-dp[D^(<<j)],dp[D]);
}
jian(j);
}
}
int main()
{ while(scanf("%d%d%d",&G,&B,&S)&&G+B+S!=)
{
if(B==){
printf("0\n");continue;
}
for(int i=; i<B; i++)
{
int d;
scanf("%d",&d);
memset(P[i],,sizeof(P[i]));
for(int j=;j<d; j++){
int k;scanf("%d",&k);
P[i][k]++;
}
}
int K=<<B;
memset(use,false,sizeof(use));
use[]=true;
int ge1=work3();
dfs(K-,ge1);
int ge=dp[K-];
printf("%d\n",ge*-ge1);
} return ;
}
最新文章
- markdown 使用
- 【C语言入门教程】4.10 综合实例 - 媒体播放器
- 【hihoCoder】1049.后序遍历
- 基于FreeBSD 64位内核的kFreeBSD无法在Virtualbox下安装
- 使用X-UA-Compatible来设置IE浏览器兼容模式
- NSThread - (void)start vs java Thread implements Runnable
- 20145120 《Java程序设计》第2周学习总结
- 【PHP高效搜索专题(2)】sphinx&;coreseek在PHP程序中的应用实例
- hibernate AOP
- ECharts地图详解 【转】
- android 设备唯一码的获取,Cpu号,Mac地址
- Unity Easy Save简单实用
- docker安装使用
- C#入门经典第八章面向对象编程简介-1
- NYoj1058
- Python数据分析(二): Numpy技巧 (3/4)
- VS2017添加引用报错
- nc工具使用
- Spring MVC 原理探秘 - 容器的创建过程
- 【Java每日一题】20170329