poj3616 动态规划

水深无声 2022-08-03 05:14 143阅读 0赞

跟hdu1087很像，感觉像一个类型的题目

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    struct st
    {
        int l;int r;
        int val;
    }a[1002];
    
    int dp[1002];   //dp[i]表示以a[i].r为结尾的最大最大值
    bool cmp(const st& a,const st& b)
    {
        return a.l<b.l;
    }
    int main()
    {
        int n,m,r;
        while(~scanf("%d%d%d",&n,&m,&r))
        {
            for(int i=0;i<m;i++)
            {
                a[i].l=in();
                a[i].r=in()+r;
                a[i].val=in();
            }
            sort(a,a+m,cmp);
            for(int i=0;i<m;i++)
            {
                dp[i]=a[i].val;
                for(int j=0;j<i;j++)
                {
                    if(a[j].r<=a[i].l) dp[i]=max(dp[i],dp[j]+a[i].val);
                    //else dp[i]=max(dp[j],dp[i]);
                }
            }
            int ans=-inf;
            for(int i=0;i<m;i++)ans=max(ans,dp[i]);
    
            printf("%d\n",ans);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，143人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj1088 滑雪动态规划+回溯

include<iostream> include<cstdio> using namespace std; int num,n,m,a[100

╰+攻爆jí腚メ/ 2024年02月17日 19:27/ 0 赞/ 37 阅读

相关 ACM学习-POJ-动态规划题集

[POJ 动态规划题目列表][POJ] 声明： 1.这份列表当然不是我原创的，从文库里下载了一份，放到这里便于自己浏览和查找题目。 ※最近更新：Poj斜率优化题目

- 日理万妓/ 2022年09月02日 11:48/ 0 赞/ 165 阅读

相关 poj 动态规划题目列表及总结

此文转载别人，希望自己能够做完这些题目！ 1.POJ动态规划题目列表容易：1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163,

落日映苍穹つ/ 2022年08月27日 01:13/ 0 赞/ 226 阅读

相关 poj 1065 贪心或者动态规划

Wooden Sticks <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000M

偏执的太偏执、/ 2022年08月03日 11:55/ 0 赞/ 188 阅读

相关 poj 3181 动态规划

Dollar Dayz <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

川长思鸟来/ 2022年08月03日 08:23/ 0 赞/ 149 阅读

相关 poj 3280 字符串上的动态规划

添加或者删除一些字母，使这个字符串变成回文串。每个字母添加和删除的代价不一样。问最小代价。看别人的思路，在字符串两端删除和添加字母是等价的，因此只需要保留删除和添加中最小的

谁践踏了优雅/ 2022年08月03日 05:14/ 0 赞/ 154 阅读

相关 poj3616 动态规划

跟hdu1087很像，感觉像一个类型的题目 include<map> include<vector> include<cstdio>

水深无声/ 2022年08月03日 05:14/ 0 赞/ 144 阅读

相关 POJ 1185(动态规划-状压dp)

问题描述: 司令部的将军们打算在N\M的网格地图上部署他们的炮兵部队。一个N\M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），

忘是亡心i/ 2022年06月01日 11:13/ 0 赞/ 179 阅读

相关 POJ 3254(动态规划-状压dp）

问题描述: Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤

短命女/ 2022年06月01日 02:49/ 0 赞/ 206 阅读

相关 dp打开思路3：HDU1069 POJ3616 POJ1088

HDU 1069 题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1069][http_acm.hdu.edu.cn_show

Bertha 。/ 2022年05月16日 08:58/ 0 赞/ 164 阅读