rnqoj-99-配置魔药-dp

比较好的题目~~

dp[j][k]: 第一个容器在第i秒和第二个容器在第j秒，所产生的最大魔力.

if(num[i].t2<=j)dp[j][k]=max(dp[j][k],dp[num[i].t1-1][k]+num[i].w);
if(num[i].t2<=k)dp[j][k]=max(dp[j][k],dp[j][num[i].t1-1]+num[i].w);

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

struct list

{

    int t1;

    int t2;

    int w;

}num[101];

int cmp(struct list a,struct list b)

{

    if(a.t2!=b.t2)return a.t2<b.t2;

    else return a.t1<b.t1;

}

int dp[501][501];

int main()

{

    int t,n,i,j,k;

    while(~scanf("%d%d",&t,&n))

    {

        for(i=0;i<n;i++)

        {

            scanf("%d%d%d",&num[i].t1,&num[i].t2,&num[i].w);

        }

        sort(num,num+n,cmp);

        memset(dp,0,sizeof(dp));

        for(i=0;i<n;i++)

        {

            for(j=t;j>=0;j--)

            {

                for(k=t;k>=0;k--)

                {

                    if(num[i].t2<=j)dp[j][k]=max(dp[j][k],dp[num[i].t1-1][k]+num[i].w);

                    if(num[i].t2<=k)dp[j][k]=max(dp[j][k],dp[j][num[i].t1-1]+num[i].w);

                }

            }

        }

        cout<<dp[t][t]<<endl;

    }

}

巴特西

rnqoj-99-配置魔药-dp

最新文章

热门文章