G.Interference Signal
时间限制: 2 Sec 内存限制: 128 MB
提交: 47 解决: 18
[提交][状态]
题目描述
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.
输入
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
输出
the maximum average strength
样例输入
2
10 6
6
4
2
10
3
8
5
9
4
1
5 2
10
3
8
5
9
样例输出
6500
7333
题目大意： 求连续序列大于等于k个的最大平均 值
dp[i][j] 表示在j的位置的i个连续序列的最大和 dp[i][j] = max(dp[i-1][j-1] + a[j], dp[i][j]) 只要公式推出来就很容易了
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include <queue> using namespace std;
#define N 2500
#define ESP 1e-8
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a)) int a[N];
int dp[N][N]; int main()
{
int T,n,k;
scanf ("%d", &T);
while(T --)
{
scanf("%d %d", &n, &k);
for(int i=; i<=n; i++)
scanf("%d", &a[i]); memset(dp, ); dp[][]=a[]; for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
dp[i][j] = max(dp[i][j], dp[i-][j-]+a[j]);
}
} double Max=; for(int i=k; i<=n; i++)
{
for(int j=i; j<=n; j++)
{
Max = max(Max, dp[i][j]*1.0/i*1.0);
}
} printf("%d\n", (int)(Max*1000.0));
}
return ;
}