<HAOI2008>硬币购物
2024-08-26 22:28:02
和神奇dp的战斗
还有容斥原理
终于get到了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
int c[],d[],tot,s;
long long dp[];
int main()
{
int i,j,k;
for(i=;i<=;i++)scanf("%d",&c[i]);
dp[]=;
for(i=;i<=;i++)
for(j=c[i];j<=;j++) dp[j]+=dp[j-c[i]];//背包aoaoaoaoaoaoao
scanf("%d",&tot); for(k=;k<=tot;k++)
{
long long ans=; for(i=;i<=;i++)scanf("%d",&d[i]);
scanf("%d",&s);
for(i=;i<=;i++)
{
long long t=s;
int cnt=;
for(j=;j<=;j++)if((i>>(j-))&)t-=c[j]*(d[j]+),cnt^=;
if(t<) continue;
if(!cnt) ans+=dp[t];else ans-=dp[t];
}
printf("%lld\n",ans);
} return ;
}
最新文章
- JAVA object
- Query Designer:Hierarchy层级显示
- weixin 公众平台开发
- OC与JS的交互
- shared_ptr<;>; reset
- php empty isset is_null
- openfire的配置
- C#中使用visio控件
- 转载 从Http到Https
- 部署解决方案包 (SharePoint Server 2010)
- 12 hdfs常用文件、目录拷贝操作、删除操作
- docker managed volume - 每天5分钟玩转 Docker 容器技术(40)
- JPA学习-03
- Ubuntu下导入PySpark到Shell和Pycharm中(未整理)
- sonar——Synchronized classes Vector, Hashtable, Stack and StringBuffer should not be used
- os模块,os.path模块,subprocess模块,configparser模块,shutil模块
- 美化checkbox多选框
- Inside GDALAllRegister之四: 跳过driver
- WCF 快速入门
- SQLAlchemy中filter()和filter_by()的区别