一些 DP 水题

现在的位置: 首页 > 综合 > 正文

RSS

2017年10月11日 ⁄ 综合 ⁄ 共 1475字 ⁄ 字号小中大 ⁄ 评论关闭

图片题目来自dd

rqnoj99 配置魔药

题目描述

【问题描述】

在《Harry Potter and the Chamber of Secrets》中，Ron的魔杖因为坐他老爸的Flying Car撞到了打人柳，不幸被打断了，从此之后，他的魔杖的魔力就大大减少，甚至没办法执行他施的魔咒，这为Ron带来了不少的烦恼。这天上魔药课，Snape要他们每人配置一种魔药（不一定是一样的），Ron因为魔杖的问题，不能完成这个任务，他请Harry在魔药课上(自然是躲过了Snape的检查)帮他配置。现在Harry面前有两个坩埚，有许多种药材要放进坩埚里，但坩埚的能力有限，无法同时配置所有的药材。一个坩埚相同时间内只能加工一种药材，但是不一定每一种药材都要加进坩埚里。加工每种药材都有必须在一个起始时间和结束时间内完成（起始时间所在的那一刻和结束时间所在的那一刻也算在完成时间内），每种药材都有一个加工后的药效。现在要求的就是Harry可以得到最大的药效。

出自:宜昌一中

输入格式

【输入】

输入文件的第一行有2个整数，一节魔药课的t（1≤t<≤500）和药材数n（1≤n≤100）。

输入文件第2行到n+1行中每行有3个数字，分别为加工第i种药材的起始时间t1、结束时间t2、（1≤t1≤t2≤t）和药效w（1≤w≤100）。

输出格式

【输出】

输出文件medic.out只有一行，只输出一个正整数，即为最大药效。

用f[i][j][k]表示第i个物品，第一个坩埚到时间j，第二个坩埚到时间k得到的最大价值。

k个坩埚的话可以转成费用流！

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
using namespace std;  
const int maxt = 500 + 10;  
const int maxn = 100 + 10;  
struct tnode  
{  
    int l,r;  
    int w;  
}medi[maxn];  
int f[maxn][maxt][maxt];  
int t,n;  
  
void init()  
{  
    freopen("rqnoj99.in","r",stdin);  
    freopen("rqnoj99.out","w",stdout);  
}  
  
int cmp(const void *a,const void *b)  
{  
    return (*(tnode *)a).l - (*(tnode *)b).l;  
}  
  
void readdata()  
{  
    scanf("%d%d",&t,&n);  
    for(int i = 1;i <= n;i++)  
    {  
        scanf("%d%d%d",&medi[i].l,&medi[i].r,&medi[i].w);  
    }  
}  
  
int max(int a,int b)  
{  
    return a > b ? a : b;  
}  
  
void solve()  
{  
    qsort(&medi[1],n,sizeof(medi[0]),cmp);  
    for(int i = 1;i <= n;i++)  
    {  
        for(int j = 0;j <= t;j++)  
        {  
            for(int k = 0;k <= t;k++)  
            {  
                f[i][j][k] = f[i-1][j][k];  
                if(j >= medi[i].r)  
                {  
                    f[i][j][k] = max(f[i][j][k],f[i-1][medi[i].l-1][k] + medi[i].w);  
                }  
                if(k >= medi[i].r)  
                {  
                    f[i][j][k] = max(f[i][j][k],f[i-1][j][medi[i].l-1] + medi[i].w);  
                }  
            }  
        }  
    }  
    printf("%d",f[n][t][t]);  
}  
  
int main()  
{  
    init();  
    readdata();  
    solve();  
    return 0;  
}