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("
");
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
",ans);
45         
46         }
47     return 0 ;
48 }

View Code

没有梦想，何谈远方