首页 > 代码库 > HDU4970 Killing Monsters dp
HDU4970 Killing Monsters dp
题意:给你n个操作,每一次对区间相加,询问区间和。
解题思路:这里没有动态更新, 所以我们用括号匹配那种方法就行 就是 a[l] + x ,a[r+1] -x 这种做法。
解题代码:
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #define MAX 100005 6 #define LL long long 7 LL a[100005]; 8 int main() 9 {10 int n;11 while(scanf("%d",&n) != EOF,n)12 {13 memset(a,0,sizeof(a));14 int tsum ;15 scanf("%d",&tsum);16 for(int i =1 ;i<=tsum ;i ++)17 {18 int ta,tb,tc;19 scanf("%d %d %d",&ta,&tb,&tc);20 a[ta] += tc;21 a[tb+1] -= tc;22 }23 LL sum = 0 ;24 LL ta = 0 ; 25 for(int i = 1;i <= n;i ++)26 {27 ta += a[i];28 sum += ta;29 a[i] = sum;30 //printf("%I64d ",a[i]);31 }32 //printf("\n");33 scanf("%d",&tsum);34 int ans = 0 ; 35 for(int i = 1;i <= tsum ;i ++)36 {37 LL ta,tb;38 scanf("%I64d %I64d",&ta,&tb);39 if(a[n] - a[tb-1] < ta)40 {41 ans ++ ;42 }43 }44 printf("%d\n",ans);45 46 }47 return 0 ;48 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。