1175: 金明的预算方案

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

int main()

{

    int n,m; cin>>n>>m;

    int sum=1,sum2=1;//主件价值,主件价钱的次数

    int a[10000],a1[10000];

    int w,v,p;

    int dp[10000];

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

    {

        cin>>w>>v>>p;

        int qq=0;//价值

        qq=w*v;

        if(!p)//主件

        {

            a1[sum2++]=w;

            a[sum++]=qq;

        }

        else//附件额外加到主件上

        {

            a1[p]+=w;

            a[p]+=qq;

        }

    }

    for(int i=1;i<=sum;i++)//dp[]数组基本操作

    {

        for(int j=n;j>=a1[i];j--)

        {

            dp[j]=max(dp[j],dp[j-a1[i]]+a[i]);

        }

    }

    cout<<dp[n];

    return 0;

}