多校2 I love exam

HDU - 6968
共有n个科目,m套复习题。一套复习题对应一个科目,用时K天,可以获得J分。一个科目分数达不到60,即为挂科。问在X天,挂科数不超过Y科的情况下,最多能获得多少分?
01背包,求出在X天,每科可以获得最多分。
再求在挂科不超过Y,X天的情况下的最高分。

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int w[16000],v[16000];
    int num;
} q[55];
int dp[55][550];
int g[55][505][4];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(dp,-0x3f,sizeof(dp));
        memset(g,-0x3f,sizeof(g));
        map<string,int> mp;
        string s;
        int n,i,j,l=1,a,b,m,k,t,f,P;
        scanf("%d",&n);
        for(i=0; i<n; i++)
        {
            cin>>s;
            mp[s]=l;
            q[i].num=0;
            l++;
        }
        scanf("%d",&P);
        while(P--)
        {
            cin>>s;
            int k=mp[s];
            int x=q[k].num;
            scanf("%d %d",&a,&b);
            q[k].w[x]=b;
            q[k].v[x]=a;
            q[k].num++;
        }
        scanf("%d %d",&m,&k);
        for(i=1; i<l; i++)
        {
            dp[i][0]=0;
            for(j=0; j<q[i].num; j++)
            {
                for(t=m; t>=q[i].w[j]; t--)
                {
                     dp[i][t]=min(100,max(dp[i][t],dp[i][t-q[i].w[j]]+q[i].v[j]));
                }
            }
        }
        g[0][0][0]=0;
        for(i=1; i<l; i++)
            for(j=0; j<=m; j++)
                for(int x=0; x<=k; x++)
                    for(f=0; f<=j; f++)
                    {
                        if(dp[i][f]>=60)
                        {
                            g[i][j][x]=max(g[i][j][x],g[i-1][j-f][x]+dp[i][f]);
                        }
                        else if(x)
                        {
                            g[i][j][x]=max(g[i][j][x],g[i-1][j-f][x-1]+dp[i][f]);
                        }
                    }
        int ans=-1;
        for(i=0; i<=k; i++)
            ans=max(ans,g[n][m][i]);
        printf("%d\n",ans);
    }

}

上一篇:css3 多种奇特效果


下一篇:编程中的观察者模式和发布订阅模式