Costume Party

来源：宝玛科技网

Description

It's Halloween! Farmer John is taking the cows to a costume party, but unfortunately he only has one costume. The costume fits precisely two cows with a length of S (1 ≤ S ≤ 1,000,000). FJ has N cows (2 ≤ N ≤ 20,000) conveniently numbered 1..N; cow i has length L_i (1 ≤ L_i ≤ 1,000,000). Two cows can fit into the costume if the sum of their lengths is no greater than the length of the costume. FJ wants to know how many pairs of two distinct cows will fit into the costume.

Input

* Line 1: Two space-separated integers: N and S
* Lines 2..N+1: Line i+1 contains a single integer: L_i

Output

* Line 1: A single integer representing the number of pairs of cows FJ can choose. Note that the order of the two cows does not matter.

Sample Input

Sample Output

状态：

d[i][j]表示前i分疲劳值为j时最大值

状态转移方程：

d[i][j]=d[i-1][j-1]+a[i]

d[i][0]=max{d[i-j][j]} j<=m&&j<i

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[10005][501];
int main(){
	int n,m;
	//memset(e,0,sizeof(e));
	memset(dp,0,sizeof(dp));
	scanf("%d%d",&n,&m);
	int x;
	for(int i=1;i<=n;i++){
	    scanf("%d",&x);
	    dp[i][0]=dp[i-1][0];
	    for(int j=1;j<=m;j++){
	    	if(j<i) dp[i][0]=max(dp[i][0],dp[i-j][j]);
	    	dp[i][j]=dp[i-1][j-1]+x;
	    }
	}
	printf("%d\n",dp[n][0]);
	return 0;
}

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文