配置魔药(DP)

2023-12-25 16:18

文章标签 配置 dp 魔药

本文主要是介绍配置魔药(DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

配置魔药【问题描述】
在《Harry Potter and the Chamber of Secrets》中，Ron的魔杖因为坐他老爸的Flying
Car撞到了打人柳，不幸被打断了，从此之后，他的魔杖的魔力就大大减少，甚至没办法执行他施的魔咒，这为Ron带来了不少的烦恼。这天上魔药课，Snape要他们每人配置一种魔药（不一定是一样的），Ron因为魔杖的问题，不能完成这个任务，他请Harry在魔药课上(自然是躲过了Snape的检查)帮他配置。现在Harry面前有两个坩埚，有许多种药材要放进坩埚里，但坩埚的能力有限，无法同时配置所有的药材。一个坩埚相同时间内只能加工一种药材，但是不一定每一种药材都要加进坩埚里。加工每种药材都有必须在一个起始时间和结束时间内完成（起始时间所在的那一刻和结束时间所在的那一刻也算在完成时间内），每种药材都有一个加工后的药效。现在要求的就是Harry可以得到最大的药效。
【输入文件】(medic.in)
输入文件的第一行有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)
输出文件medic.out只有一行，只输出一个正整数，即为最大药效。
【输入样例】
7 4
1 2 10
4 7 20
1 3 2
3 7 3
【输出样例】
35
【注释】
本题的样例是这样实现的：第一个坩埚放第1、4种药材，第二个坩埚放第2、3种药材。这样最大的药效就为10+20+2+3=35。
【数据规模】
对于30%的数据
1<=t<=500
1<=n<=15
1<=w<=100
1<=t1<=t2<=t
对于100%的数据
1<=t<=500
1<=n<=100
1<=w<=100
1<=t1<=t2<=t

/*
DP.
这题一开始想前i个物品
1锅放j个2锅放k个的最优值.
然后不知道最后是谁放的
没法通过状态转移(就得开5维了orz)
f[i][j][k]直接表示
前i个物品1锅最后放j 2锅最后放k的最优值.
先排一遍序不然乱序转移没法搞. 
然后跑背包就可以了.. 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 101
using namespace std;
int f[MAXN][MAXN][MAXN],n,m,ans;
struct data{int x,y,z;}s[MAXN];
bool cmp(const data &x,const data &y)
{if(x.x!=y.x)return x.x<y.x;return x.y<y.y;
}
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f;
}
int main()
{m=read();n=read();for(int i=1;i<=n;i++)s[i].x=read(),s[i].y=read(),s[i].z=read();sort(s+1,s+n+1,cmp);for(int i=1;i<=n;i++)for(int j=0;j<i;j++)for(int k=0;k<i;k++){if(s[j].y<s[i].x)f[i][i][k]=max(f[i-1][i][k],f[i-1][j][k]+s[i].z);if(s[k].y<s[i].x)f[i][j][i]=max(f[i-1][j][i],f[i-1][j][k]+s[i].z);ans=max(ans,max(f[i][i][k],f[i][j][i]));}printf("%d",ans);return 0;
}