Skip to content

11299: 【原1299】酝酿算法

题目

题目描述

author: Xihu Zhang 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1299

Description

Black Yellow Bar!

Yellow哥喜欢酝酿算法。

很久很久以前,在Yellow哥还不那么出名的时候。他和基友们参加了某场ACM区域赛。比赛战况十分激烈,已经有一支队伍切了7题了。而Yellow哥的队伍才5题。 Yellow哥的队友们一直在努力Debug但仍然查不出错。看着队友们的艰辛努力和其它队伍对他们的肆意践踏,Yellow哥这就不能忍了。酝酿下算法,转身扔出代码,完成五杀!以10题AK结束了这场比赛。

其实切题是其次,Yellow哥喜欢用有威慑力的算法来碾碎其它队伍的自尊。但某些算法需要一些前置算法的支持。(如:写块状链表肯定要支持普通链表的操作)在这里,我们假设Yellow哥有M个算法思想,编号1到M。每个算法思想最多只有一个前置算法,对于一个拥有前置算法的算法,如果没有使用前置算法。这个算法也将不能使用。每个算法有个思考时间ti,和算法威慑力di,以及它的前置算法思想编号pi(pi=0表示该算法没有前置算法,可以自由使用)。而且,只要给Yellow哥无限长的时间,他可以想出所有M个算法,即不存在一个算法的直接或间接的前置算法包含它自己。可惜Yellow哥在ACM赛场上只有N个单位的时间。而当时,Yellow哥以自己强大的能力给予了全场以最大的威慑。

为了还原真相,请计算出Yellow哥当时选用的算法总的威慑力是多少。

Input Format

第一行两个整数N,M。 接下来的M行中,第i行给出的是第i种算法的ti,di,pi。

Output Format

一个数,表示Yellow哥给出的最大算法威慑力总和。

Sample Input

1000 5
800 1600 0
400 2000 1
300 1500 1
400 1200 0
500 1000 0

Sample Output

2200

Sample Illustration

Yellow哥扔出第4、5个算法,发出总和为2200的威慑力。

无法单独选择第2、3个算法,因为它们无法在第1个算法使用前使用。

Hint

30%的数据:N≤300、M≤10。

50%的数据:N≤500、M≤30。

100%的数据:N≤30000、M≤300,所有输入数据为正整数且小于32768.

WashSwang's solution

#include <iostream>
using namespace std;
int dp[301][30001],power[301],ti[301],n,m,nxt[1000],last[1000],to[1000],num,p,ans;
void add(int u,int v){
    ++num;
    nxt[num]=last[u];
    last[u]=num;
    to[num]=v;
}
void dfs(int x,int v){
    if (v<0) return;
    for (int i=last[x];i;i=nxt[i]){
        int t=to[i];
        for (int j=0;j<=v;++j) dp[t][j]=dp[x][j];
        dfs(t,v-ti[t]);
        for (int j=ti[t];j<=v;++j) dp[x][j]=max(dp[x][j],dp[t][j-ti[t]]+power[t]);
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i) {
        scanf("%d%d%d", &ti[i], &power[i], &p);
        add(p,i);
    }
    dfs(0,n);
    for (int i=0;i<=n;++i)
        if (ans<dp[0][i]) ans=dp[0][i];
    printf("%d",ans);
    return 0;
}