[百度]罪犯转移

时间限制：1秒 空间限制：32768K 热度指数：34020

本题知识点： 动态规划

题目描述

C市现在要转移一批罪犯到D市，C市有n名罪犯，按照入狱时间有顺序，另外每个罪犯有一个罪行值，值越大罪越重。现在为了方便管理，市长决定转移入狱时间连续的c名犯人，同时要求转移犯人的罪行值之和不超过t，问有多少种选择的方式？

输入描述:

第一行数据三个整数:n，t，c(1≤n≤2e5,0≤t≤1e9,1≤c≤n)，第二行按入狱时间给出每个犯人的罪行值a

_i

(0≤a

_i

≤1e9)

输出描述:

一行输出答案。

输入例子:

3 100 2
1 2 3

输出例子:

2
思路：
利用动态规划的思想解决，首先计算前c个罪行值之和，然后每移动一个单位，减去第一个元素，再加上新增加的元素。

#include<iostream>  
#include<vector>  
  
using namespace std;  

int main()
    {
       int n,t,c,a;
       while(cin>>n>>t>>c)
           {
              vector<int> cri;//用来存罪犯的罪行值
              for(int i=0;i<n;++i)
                  {
                     cin>>a;
                     cri.push_back(a);
                  
              }
           int count=0;
           int sum=0;
           
           for(int i=0;i<c;++i)
               {
                 sum+=cri[i];
               
           }
           if(sum<=t)
               ++count;
           for(int i=1;i<=cri.size()-c;++i)
               {
                  sum-=cri[i-1];
                  sum+=cri[i+c-1];
                  if(sum<=t)
                      ++count;
               
           }
           cout<<count<<endl;
       }
    return 0;
}