G.Interference Signal---河南省第八届程序设计大赛(dp)

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 ;
}
 
上一篇:【论文笔记】CBAM: Convolutional Block Attention Module


下一篇:(zhuan) 自然语言处理中的Attention Model:是什么及为什么