首页 > 代码库 > HDU4970 Killing Monsters dp

HDU4970 Killing Monsters dp

2024-07-18 12:01:35   228人阅读

题意：给你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 }
View Code

 


联系
我们