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]的最大值。

 

#include
#include
#include
#include
using namespace std;
const long long maxn=20;
long long dp[(1<<maxn)][maxn];
long long v[maxn];
long long pp[maxn][maxn];
long long n,m,k;
long long max(long long x,long long y)
{
    if(xreturn y;
    return x;
}
long long _count(long long x)
{
    long long an=0;
    while(x)
    {            
        if(x&1)an++;
        x>>=1;
    }
    return an;
}
int main()
{
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    scanf("%I64d%I64d%I64d",&n,&m,&k);
    for(int i=0;i<=n-1;i++)
    scanf("%I64d",&v[i]);
    for(int i=1;i<=k;i++)
    {
        int x,y;long long z;
        scanf("%d%d%I64d",&x,&y,&z);
        pp[x-1][y-1]=z;
    }
    long long ans=0;
    for(int i=0;i<=n-1;i++)
    dp[(1<v[i];
    for(int i=0;i<(1<)
    {
        int qw=_count(i);
        if(qw>m)continue;
        if(qw==m)
        {
            for(int j=0;j<=n-1;j++)
            ans=max(ans,dp[i][j]);
            continue;        
        }
        else
        {
            for(int j=0;j<=n-1;j++)//枚举没有吃的
            {
                if(((1<0)//没有吃
                {
                    for(int k=0;k<=n-1;k++)//枚举最后吃的点
                    if(((1<//吃过 
                    dp[i|(1<1<<j)][j]);
                } 
            }
            
        }
    }
    printf("%I64d",ans);
    return 0;
}