首页 > 其他分享 >HDU 1176 免费馅饼(简单动态规划)

HDU 1176 免费馅饼(简单动态规划)

时间:2023-05-26 15:07:32浏览次数:51  
标签:1176 HDU 数塔 int max ++ maxt 馅饼 include


传送门

这道题是中文描述的,我相信大家都肯定能够看得懂(滑稽),思路上呢大概就是一个升级版的数塔(点我去看数塔)既然是动态规划问题所以首先肯定要先找出来状态转移方程,我找到的状态转移方程就是a[i][j] += max(max(a[i+1][j+1],a[i+1][j]),a[i+1][j-1]),其中a[i][j]就是表示第i时刻在k位置所能够得到的最大的馅饼数。建议大家先做完数塔再来,比较好理解这个思路,好了话不多说。

代码如下

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
    int n,a[100005][12];
    while(scanf("%d",&n) && n)
    {
        memset(a,0,sizeof(a));
        int maxt = 0;
        for(int i = 0;i < n; i++)
        {
            int x,t;
            scanf("%d %d",&x,&t);
            a[t][x]++;
            if(t > maxt)
                maxt = t;
        }
        for(int i = maxt - 1;i >= 0; i--)
        {
            a[i][0] += max(a[i+1][0],a[i+1][1]);
            for(int j = 1;j < 11; j++)
                a[i][j] += max(max(a[i+1][j+1],a[i+1][j]),a[i+1][j-1]);
        }
        printf("%d\n",a[0][5]);
    }
    return 0;
}

 

标签:1176,HDU,数塔,int,max,++,maxt,馅饼,include
From: https://blog.51cto.com/u_16131191/6356099

相关文章

  • HDU 1029 Ignatius and the Princess IV(基础dp)
    传送门题目大意就是给你n个数(保证n为一个奇数),存在一个数出现的次数大于(n+1)/2次,求这个数;这个数出现的次数比其他数出现的次数加起来还多,那么当这个数出现时+1,其他的数出现时-1,最后得到的数为正数。假定一个数为特殊数,若当前数与特殊数相同则cnt++,若不相同则cnt--,如果这时cnt<0,用当......
  • HDU 2084 数塔(动态规划入门)
    传送门中文题就不给大家翻译了(手动滑稽),反正大家都看得懂。这是一道动态规划入门的题目,只需要找出状态转移方程即可。状态方程:dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j])(dp[i][j]表示从第i层第j个数开始搜能得到的最大数)代码如下:#include<cstring>#include<iostream>#include<......
  • HDU 1024 Max Sum Plus Plus(动态规划)
    传送门题意是给你个数字序列,现在让你把这个序列分成m个连续的子序列,且要求这m个子序列的累加和最大。思路:这道题的题意可以理解为问在序列为末尾时,把序列分为m个子序列这个状态时的最大累加和,那么可以得出这个状态应该是由上一个状态转移得来:(因为dp[i][j]表示数到第j个字符时,前j个......
  • hdu 4758 Walk Through Squares(AC自动机+DP,4级)
    WalkThroughSquaresTimeLimit:4000/2000MS(Java/Others)    MemoryLimit:65535/65535K(Java/Others)TotalSubmission(s):234    AcceptedSubmission(s):58ProblemDescription  Onthebeamingdayof60thanniversaryofNJUST,asamilitary......
  • HDU-1003- Max Sum (动态规划)
    MaxSumTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):192050    AcceptedSubmission(s):44727ProblemDescriptionGivenasequencea[1],a[2],a[3]......a[n],yourjobistocalculatethe......
  • hdu-2680-Choose the best route(dijkstra)
    ChoosethebestrouteTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):10470    AcceptedSubmission(s):3367ProblemDescriptionOneday,Kikiwantstovisitoneofherfriends.Assheis......
  • hdu-1869-六度分离(dijkstra)
    六度分离TimeLimit:5000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):5935    AcceptedSubmission(s):2395ProblemDescription1967年,美国著名的社会学家斯坦利·米尔格兰姆提出了一个名为“小世界现象(small......
  • hdu:gcd(欧拉函数)
    ProblemDescriptionThegreatestcommondivisorGCD(a,b)oftwopositiveintegersaandb,sometimeswritten(a,b),isthelargestdivisorcommontoaandb,Forexample,(1,2)=1,(12,18)=6.(a,b)canbeeasilyfoundbytheEuclideanalgorithm.NowCarpiscon......
  • hdu:LCIS(线段树+区间合并)
    ProblemDescriptionGivennintegers.Youhavetwooperations:UAB:replacetheAthnumberbyB.(indexcountingfrom0)QAB:outputthelengthofthelongestconsecutiveincreasingsubsequence(LCIS)in[a,b].InputTinthefirstline,indicatingt......
  • hdu:这是真正的水题(RMQ)
    ProblemDescription在缺水的地方,水是非常有限的资源,所以人们常常为争夺最大的水源而战。给定一系列水源,用a1,a2,a3,…,an代表水源的大小。给定一组查询,每个查询包含2整数L和R,请找出L和R之间最大的水源。Input输入数据首先给定一个整数T(T≤10)表示测试用例的数量。......