文档章节

[离散化][区间DP]JZOJ 5770 可爱精灵宝贝

o
 osc_1ee7cxmx
发布于 2018/08/06 21:24
字数 919
阅读 13
收藏 0
go

日常黑Pokeman Go

Description

Branimirko是一个对可爱精灵宝贝十分痴迷的玩家。最近,他闲得没事组织了一场捉精灵的游戏。游戏在一条街道上举行,街道上一侧有一排房子,从左到右房子标号由1到n。
刚开始玩家在k号房子前。有m个精灵,第i只精灵在第A[i]栋房子前,分值是B[i],以及它在T[i]秒内(含)存在,之后消失。Branimirko可以选择移动至相邻的房子,耗时1秒。抓住精灵不需要时间,精灵被抓住后消失。时间从第1秒开始。Branimirko能最多获得多少分值和。
 
 

Input

输入的第1行为三个正整数n,k,m。
接下来m行描述精灵的信息,分别为A[i],B[i],T[i]。
 

Output

输出Branimirko能最多获得多少分值和。
 
 

Sample Input

10 5 4
1 30 4
3 5 7
7 10 12
9 100 23
 

Sample Output

115
 
 

Data Constraint

20%的数据:m≤10
40%的数据:m≤20
k≤n≤1000,m≤100,A[i] ≤N,B[i] ≤100,T[i] ≤2000,所有数为正整数。
 
 

Hint

很遗憾,它恰好不能抓住在一号房子前的精灵。
如果T[1]改成5,答案就是145

分析

比赛的时候居然打了一个不知道什么鬼的居然离散了时间的DP

正解区间DP,设f[l][r][t]为所用时间为t,经过了l~r,现在在r的最大分值,g[l][r][t],类似,不过在l

预处理:离散化房屋编号

然后从l~r向l-1~r或l~r+1转移

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <memory.h>
using namespace std;
int f[101][101][4001],g[101][101][4001];
struct Elf {
    int a,b,t;
}a[102];
int n,m,k,mxt,bg;

bool Cmp(Elf a,Elf b) {
    return a.a<b.a;
}
 
int main() {
    freopen("go.in","r",stdin);
    freopen("go.out","w",stdout);
    scanf("%d%d%d",&n,&k,&m);
    for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].t),mxt=max(mxt,a[i].t);
    a[0].a=k;a[0].b=0;a[0].t=1;
    sort(a,a+m+1,Cmp);
    for (int i=0;i<=m;i++)
    if (a[i].a==k&&a[i].t==1) {bg=i;break;}
    memset(f,-0x3f,sizeof f);
    memset(g,-0x3f,sizeof g);
    f[bg][bg][1]=g[bg][bg][1]=0;
    for (int t=1;t<=mxt;t++)
    for (int l=bg;l>=0;l--)
    for (int r=bg;r<=m;r++) {
        if (r<m) {
            f[l][r+1][a[r+1].a-a[r].a+t]=max(f[l][r+1][a[r+1].a-a[r].a+t],f[l][r][t]);
            f[l][r+1][a[r+1].a-a[l].a+t]=max(f[l][r+1][a[r+1].a-a[l].a+t],g[l][r][t]);
            if (a[r+1].a-a[r].a+t<=a[r+1].t)
            f[l][r+1][a[r+1].a-a[r].a+t]=max(f[l][r+1][a[r+1].a-a[r].a+t],f[l][r][t]+a[r+1].b);
            if (a[r+1].a-a[l].a+t<=a[r+1].t)
            f[l][r+1][a[r+1].a-a[l].a+t]=max(f[l][r+1][a[r+1].a-a[l].a+t],g[l][r][t]+a[r+1].b);
        }
        if (l>0) {
            g[l-1][r][a[r].a-a[l-1].a+t]=max(g[l-1][r][a[r].a-a[l-1].a+t],f[l][r][t]);
            g[l-1][r][a[l].a-a[l-1].a+t]=max(g[l-1][r][a[l].a-a[l-1].a+t],g[l][r][t]);
            if (a[r].a-a[l-1].a+t<=a[l-1].t)
            g[l-1][r][a[r].a-a[l-1].a+t]=max(g[l-1][r][a[r].a-a[l-1].a+t],f[l][r][t]+a[l-1].b);
            if (a[l].a-a[l-1].a+t<=a[l-1].t)
            g[l-1][r][a[l].a-a[l-1].a+t]=max(g[l-1][r][a[l].a-a[l-1].a+t],g[l][r][t]+a[l-1].b);
        }
    }
    int ans=0;
    for (int t=1;t<=mxt;t++)
    for (int l=bg;l>=0;l--)
    for (int r=bg;r<=m;r++)
    ans=max(ans,max(f[l][r][t],g[l][r][t]));
    printf("%d",ans);
    fclose(stdin);fclose(stdout);
}
View Code

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

pycurl libcurl link-time ssl backend (nss)

pip uninstall pycurlecho 'pycurl==7.19.5.1 --global-option="--with-nss"' > requires.pypip install -r requires.py...

小红手
39分钟前
17
0
计算机网络性能衡量

1、速率 单位时间(s)内传输信息(bit)量 单位:KB/s, MB/s, Gb/s K = 10^3 ,M = 10^6, G=10^9 一般表示的是理想的传输速率 2、带宽 计算机网络中的带宽和通信等领域的带宽概念不一样,计算机网...

osc_np3y0rbq
39分钟前
3
0
互联网掀起农家乐,巨头上演AI掘金战

配图来自Canva **前有网易、阿里AI养猪,后有腾讯AI养鹅,互联网大佬们纷纷玩起了“农家乐”,互联网的生意在尖端技术的引领之下频频跨界,巨头之间的较量也从线上延伸至线下。**自古“民以食...

osc_5cok9i01
41分钟前
9
0
原来!我在4年前就开始体验雾游戏了!

前有云游戏后有雾游戏,游戏的方式看来起来越来越多种多样。那么“震撼业界”的雾游戏到底是什么来头?它依靠什么改变游戏界?它的原理又是什么? 本月月初,著名的日本游戏杂志《Fami通》表...

osc_j34n26zn
42分钟前
11
0
活动预告|田溯宁与你相约GSMA Thrive·万物生晖,分享5G风口下的创新与投资洞察

在万物互联的时代背景下,5G+AI+IoT的技术变革与融合,正在引发一场深刻的全产业创新与变革。5G技术创新、行业应用及投资机遇已成为科技行业所瞩目的焦点。 6月30日,宽带资本董事长田溯宁将...

osc_0qnrwmy3
43分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部