G.Interference Signal
Time Limit: 2 Sec Memory Limit: 128 MB Submit: 35 Solved: 17 [Submit][Status][Web Board]
Description
Dr.Kong’s laboratory monitor some interference signals. The interference signals can be digitized into a series of positive integer. May be, there are N integers a1,a2,…,an.
Dr.Kong wants to know the average strength of a contiguous interference signal block. the block must contain at least M integers.
Please help Dr.Kong to calculate the maximum average strength, given the constraint.
Input
The input contains K test cases. Each test case specifies:
* Line 1: Two space-separated integers, N and M.
* Lines2~line N+1: ai (i=1,2,…,N)
1 ≤ K≤ 8, 5 ≤ N≤ 2000, 1 ≤ M ≤ N, 0 ≤ ai ≤9999
Output
The input contains K test cases. Each test case specifies:
* Line 1: Two space-separated integers, N and M.
* Lines2~line N+1: ai (i=1,2,…,N)
1 ≤ K≤ 8, 5 ≤ N≤ 2000, 1 ≤ M ≤ N, 0 ≤ ai ≤9999
Sample Input
2
10 6
6
4
2
10
3
8
5
9
4
1
5 2
10
3
8
5
9
Sample Output
6500
7333
HINT
Source
题解：让找长度大于等于M的连续子序列的最大平均值；
思路：简单dp，dp[i][j]=dp[i-1][j-1]+m[j];代表在j处前i个数的序列和；
然后判断找平均值；
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x)
#define SL(x) scanf("%lld",&x)
#define PI(x) printf("%d",x)
#define PL(x) printf("%lld",x)
#define P_ printf(" ")
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
typedef long long LL;
const int MAXN=2020;
int m[MAXN];
int dp[MAXN][MAXN];
double pp[MAXN][MAXN];
int main(){
int T,N,M;
SI(T);
while(T--){
SI(N);SI(M);
for(int i=1;i<=N;i++)SI(m[i]);
mem(dp,0);
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
dp[i][j]=dp[i-1][j-1]+m[j];
}
}
double x=0;
for(int i=M;i<=N;i++)
for(int j=M;j<=N;j++)
x=max(x,1.0*dp[i][j]/i);
printf("%d\n",(int)(1000*x));
}
return 0;
}