首页 > 代码库 > NOIP模拟题——B
NOIP模拟题——B
【题目描述】
我们要从n种食物选m个出来，安排一个顺序吃掉它（们），每种食物有个美味值ai，然后我们有k个规则，每个规则有 xi, yi 和 ci三个数，如果吃完第xi种食物接下来马上吃第yi种食物，第j种食物的美味值会增加ci。每种食物至多吃一个，求美味值最大的和是多少？
【输入格式】
第一行有三个数n,m,k,k代表有k个规则(0<=k<=n*(n-1))。
第二行有n个数字代表每个食物的美味值。
接下去有k行，每行三个数xi,yi,ci。保证没有任意两个规则的xi和yi同时相同。
【输出格式】
一行一个数代表答案
【sample input1】
2 2 1
1 1
2 1 1
【sample output1】
3
【sample input 2】
4 3 2
1 2 3 4
2 1 5
3 4 2
【sample output 2】
12
【数据范围】
30% m<=n<=5 ,0<=ci,ai<=1e5
100% m<=n<=18，0<=ci,ai<=1e9
由于数据小，找的多，所以考虑状压DP。f[i][j]表示i状态时最后一个数为j的最大值，若没有吃完则每次找还未吃掉的和吃掉的(看做是当前状态最后一个吃掉的)，若吃多了就continue，否则(找完m个了)找dp[i][j]的最大值。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const long long maxn=20; 7 long long dp[(1<<maxn)][maxn]; 8 long long v[maxn]; 9 long long pp[maxn][maxn];10 long long n,m,k;11 long long max(long long x,long long y)12 {13 if(x<y)return y;14 return x;15 }16 long long _count(long long x)17 {18 long long an=0;19 while(x)20 { 21 if(x&1)an++;22 x>>=1;23 }24 return an;25 }26 int main()27 {28 freopen("b.in","r",stdin);29 freopen("b.out","w",stdout);30 scanf("%I64d%I64d%I64d",&n,&m,&k);31 for(int i=0;i<=n-1;i++)32 scanf("%I64d",&v[i]);33 for(int i=1;i<=k;i++)34 {35 int x,y;long long z;36 scanf("%d%d%I64d",&x,&y,&z);37 pp[x-1][y-1]=z;38 }39 long long ans=0;40 for(int i=0;i<=n-1;i++)41 dp[(1<<i)][i]=v[i];42 for(int i=0;i<(1<<n);i++)43 {44 int qw=_count(i);45 if(qw>m)continue;46 if(qw==m)47 {48 for(int j=0;j<=n-1;j++)49 ans=max(ans,dp[i][j]);50 continue; 51 }52 else53 {54 for(int j=0;j<=n-1;j++)//枚举没有吃的55 {56 if(((1<<j)&i)==0)//没有吃57 {58 for(int k=0;k<=n-1;k++)//枚举最后吃的点59 if(((1<<k)&i))//吃过 60 dp[i|(1<<j)][j]=max(dp[i][k]+pp[k][j]+v[j],dp[i|(1<<j)][j]);61 } 62 }63 64 }65 }66 printf("%I64d",ans);67 return 0;68 }
NOIP模拟题——B
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。