A - Investment

Sample Input

1

10000 4

2

4000 400

3000 250

Sample Output

14050

思路如下

题解如下

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

struct Node

{

    int pri;

    int val;

};

Node node[100];

int main()

{

    int q;

    //cin>>q;

    scanf("%d",&q);

    while(q--)

    {

        int money,year,spci; 		//spci 为股票的种类

        //cin>>money>>year>>spci;

        scanf("%d%d%d",&money,&year,&spci);

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

        {

            int temp;

            //cin>>temp>>node[i].val;

            scanf("%d%d",&temp,&node[i].val);

            node[i].pri = temp/1000;	//除以1000缩小范围

        }

        while(year--)

        {

            int f[100005] = {0};		//状态转移方程

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

                for(int mon = node[i].pri;mon <= money/1000;mon ++)

                    f[mon] = max(f[mon],f[mon - node[i].pri ] + node[i].val);

            money += f[money/1000];

        }

        cout<<money<<endl;

    }

    return 0;

}