Comet OJ - Contest #11 B usiness

发布时间：2020-12-15 07:40:46 所属栏目：Java 来源：网络整理

导读：题目思路：很明显的dp题，就是以天数作为阶段，然后里面套一个完全背包，因为每天结束时会得到节点，所以在天数的循环最后还要加一个循环用来加上每天结束时得到的节点。 dp[u]表示现在有u个节点时最后能得到多少个节点,有几个地方要注意，首先是当前有的

题目思路：

很明显的dp题，就是以天数作为阶段，然后里面套一个完全背包，因为每天结束时会得到节点，所以在天数的循环最后还要加一个循环用来加上每天结束时得到的节点。

dp[u]表示现在有u个节点时最后能得到多少个节点,有几个地方要注意，首先是当前有的节点数要从2000开始循环，因为w[i]和k的范围是1000，假如说当前有1000个节点，那么又得到1000个节点，所以最多可能有2000个节点（大于k得到的节点是0）。其次是最后加上每天得到的节点数时要取一个最大值。最后答案要记得加上当前有的节点数。

代码：

#include<bits/stdc++.h>
using namespace std;
int dp[10010],w[10010],n,m,k,ans;
pair<int,int>p[101];//代表题目中的ai,bi
int main()
{
    memset(dp,128,sizeof(dp));
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 0;i<=k;i++)
        scanf("%d",&w[i]);
    for(int i = 1;i<=m;i++)
        scanf("%d%d",&p[i].first,&p[i].second);
    dp[0] = 0;
    for(int i = 1;i<=n;i++)//天数
    {
        for(int j = 1;j<=m;j++)//存储方式
            for(int u = 2000;u>=0;u--)//当前有的节点数
                dp[u] = max(dp[u],dp[u+p[j].first]+p[j].second);
        for(int u = 2000;u>=0;u--)//加上当天结束得到的节点数
            dp[u+w[u]] = max(dp[u+w[u]],dp[u]);
    }
    for(int i = 0;i<=2000;i++)
        ans = max(ans,dp[i]+i);//最后答案等于最后得到的节点加上当前有的节点
    printf("%d",ans);
    return 0;  
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!