codevs1005 生日礼物

特殊节日礼物：提前规划节日礼物清单 #生活知识# #购物技巧# #购物清单制作#

36

/*DFS搜索

include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

struct node

{

int p[15],num;

}map[15];

int ans=1001,n,m;

int reach[20],num[15];

bool cmp(node a,node b)

{

for(int i=1;i<=m;i++)

if(a.p[i]!=b.p[i])return a.p[i]<b.p[i];

return a.num>b.num;

}

bool check()

{

for(int i=1;i<=m;i++)

if(reach[i]==0)return false;

for(int i=1;i<m;i++)

if(reach[i]!=reach[i+1])return false;

ans=min(ans,reach[1]*m);

return true;

}

void dfs(int u)

{

if(u==n+1)

{

check();

return;

}

if(check())return;

for(int i=0;i<=map[u].num;i++)

{

for(int j=1;j<=m;j++)

{

reach[j]+=map[u].p[j]*i;

if(reach[j]*m>=ans)

{

for(int k=1;k<=j;k++)

reach[k]-=map[u].p[k]*i;

return;

}

}

dfs(u+1);

for(int j=1;j<=m;j++)

reach[j]-=map[u].p[j]*i;

}

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

scanf("%d",&map[i].p[j]);

for(int i=1;i<=n;i++)

scanf("%d",&map[i].num);

sort(map+1,map+n+1,cmp);

dfs(1);

if(ans==1001)printf("alternative!\n");

else printf("%d\n",ans);

return 0;

}

网址：codevs1005 生日礼物 https://www.yuejiaxmz.com/news/view/809170

相关内容

【生日礼物diy】生日礼物diy价格
10个有创意的生日礼物 生日礼物
DIY生日礼物，手工DIY生日礼物送女生
自制生日礼物，手工创意生日礼物DIY
DIY生日礼物
diy生日礼物还有有创意diy生日礼物
生日礼物、情人节礼物、圣诞礼物！小组
创意生日礼物diy或者创意生日礼物手工
生日创意礼物推荐,简单创意的生日礼物
生日礼物自制

随便看看