本文主要是介绍hdu 1176 免费馅饼,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1176
免费馅饼
Problem Description
Input
输入数据有多组。每组数据的第一行为以正整数n(0<n<100000),表示有n个馅饼掉在这条小径上。在结下来的n行中,每行有两个整数x,T(0<T<100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。
Output
每一组输入数据对应一行输出。输出一个整数m,表示gameboy最多可能接到m个馅饼。
提示:本题的输入数据量比较大,建议用scanf读入,用cin可能会超时。
提示:本题的输入数据量比较大,建议用scanf读入,用cin可能会超时。
Sample Input
6 5 1 4 1 6 1 7 2 7 2 8 3 0
Sample Output
4
数塔问题:(数字三角形)
dp:
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100005;int n,T,a[maxn][15];void solve(){for(int i=T-1;i>=0;i--)for(int j=1;j<=11;j++){int tmp=max(a[i+1][j],a[i+1][j+1]);tmp=max(tmp,a[i+1][j-1]);a[i][j]+=tmp;}
}
int main(){while(scanf("%d",&n)&&n){T=0;memset(a,0,sizeof(a));for(int i=0;i<n;i++){int x,t;scanf("%d%d",&x,&t);T=max(T,t);a[t][x+1]+=1;}solve();printf("%d\n",a[0][6]);}return 0;
}
试了一下新学的随机化算法卡时,貌似不是很好使
这篇关于hdu 1176 免费馅饼的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!