SumoandVirus

NC207572. SumoandVirus

描述

Sumo生活的小镇有m个居民，小镇的生活和谐而美好。但是，有一天，可怕的事情发生了......
这个故事要从一只蝙蝠讲起。
一个月黑风高的夜晚，Sumo家中闯入了一只迷路的蝙蝠，Sumo在驱赶蝙蝠的过程中一不小心被蝙蝠咬伤了。结果就悲剧了，他感染了一种传染性很强的病毒。现在发现这种病毒的传染情况如下：

一个病患每天可以传染x个未被感染的人；
潜伏期为7天，期间不发病也不传染别人；
第8天开始发病，并且可以传染；
第14天，被治愈（当天不会传染，且不再具有传染能力）；
治愈之后具有抵抗力，不会被传染。

问：从Sumo感染病毒开始算第一天，第n天过后小镇上有几个传染者（指具有传染能力的人）？

输入描述

第一行包含一个正整数 ，表示一共有T组数据。

第二行包含三个正整数 ，，，含义如题目所描述。

输出描述

输出一个整数代表第n天有几个传染者（指具有传染能力的人）。

示例1

输入:

输出:

0
1
3

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 22ms, 内存消耗: 748K, 提交时间: 2020-06-17 13:30:59

#include<bits/stdc++.h>
using namespace std;
 
int i,ans,T,DP[100005];
int main()
{
    long long x,n,m;
	scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld%lld",&x,&m,&n);
        DP[1]=1,m--,ans=0;
        for(i=2;i<=n;i++)
        {
            ans+=(i>7?DP[i-7]:0)-(i>13?DP[i-13]:0);
            DP[i]=min(ans*x,m),m-=DP[i];
        }
        printf("%d\n",ans);
    }
}

C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 1376K, 提交时间: 2020-06-06 21:12:47

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	int t;cin>>t;
	while(t--){
		ll x,n,m;cin>>x>>m>>n;ll sb[100005];
		ll sum=0;ll all=m-1;sb[1]=1;
		for(int i=2;i<=n;i++){
			if(i-7>=1)sum+=sb[i-7];
			if(i-13>=1)sum-=sb[i-13];
			sb[i]=min(all,sum*x);
			all-=sb[i];
			}
			cout<<sum<<"\n";
	}
}