HDU 5000 Clone

제목:
복제된 개체마다 n개의 속성이 있는데 만약에 A, B 두 개체 A의 n개 속성이 모두 B의 n개 속성보다 낮지 않으면 B는 도태되고 최대 몇 개의 개체가 동시에 생존할 수 있느냐고 묻는다.
아이디어:
데이터 크기에 맞춰서 n^2의 복잡성을 DP에 고려해보세요.
DP는 가장 좋은 집합 중의 원소의 n개 속성과 반드시 같다는 아이디어의 지원을 필요로 한다. 왜일까?가장 좋은 집합의 속성과 5를 가정해 보세요. 이때 6이나 4의 원소를 선택하면 적어도 2개와 5의 해가 집합에서 버려집니다. 1개를 넣고 2개를 버리는 것은 분명 부적합합니다. 그리고 이 가장 좋은 속성과 필연적으로 n개의 속성 최대치의 절반입니다.
모든 속성의 최대치가ti라고 가정하면sumt/2가 가장 좋은 속성이고 그러면 문제는 n개의 숫자를 추출하여 i의 숫자를 0에서ti 사이로sumt/2로 묻는 방안이 몇 가지가 있는데 이것으로DP를 할 수 있습니다.
dp[i][j]는 i번째 숫자와 j를 나타내는 방안의 수를 나타낸다. 그러면 이동하는 것은 dp[i][j]=dp[i-1][j-ti]+dp[i-1][j-ti+1]+...+pp[i-1][j] for만 사용하면 3개의 순환이 필요하지만 이것은 연속 구화식이고 트리 수조로 최적화하면 O(n^2logn)로 해결할 수 있습니다.
PS: 항저우 카드의 시간은 비교적 죽기 때문에 매번 순환할 때마다 2000까지 하지 마라 sumt/2 이후의 숫자는 모두 쓸모가 없기 때문에 계산하지 마라
코드:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<cassert>
using namespace std;
typedef long long LL;
#define Q 401
#define N 2002
#define M 200001
#define inf 2147483647
#define mod 1000000007
#define lowbit(x) (x&(-x))

int t, n, p;
int d[N];
LL f[N][N];

void add(int r, int x, int v) {
	for (; x <= p; x += lowbit(x)) {
		f[r][x] += v;
		if (f[r][x] > mod)
			f[r][x] -= mod;
	}
}

LL sum(int r, int x) {
	LL res = 0;
	for (; x > 0; x -= lowbit(x))
		res += f[r][x];
	return res % mod;
}

int main() {
	int i, j, k, tmp;
	scanf("%d", &t);
	while (t--) {
		memset(f, 0, sizeof(f));
		p = 0;
		scanf("%d", &n);
		for (i = 1; i <= n; i++) {
			scanf("%d", &d[i]);
			p += d[i];
		}
		p = p / 2 + 1;
		for (i = 1; i <= d[1] + 1; i++)
			add(1, i, 1);
		for (i = 2; i <= n; i++) {
			for (j = 1; j <= p; j++) {
				k = j - d[i] - 1;
				tmp = (sum(i - 1, j) - sum(i - 1, k) + mod) % mod;
				add(i, j, tmp);
			}
		}
		printf("%lld
", (sum(n, p) - sum(n, p - 1) + mod) % mod);
	}
	return 0;
}