P1270下载数据过了,但是在线评测过不了??!!
查看原帖
P1270下载数据过了,但是在线评测过不了??!!
35769
想当神犇的CJ楼主2022/3/9 21:52
#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
#define MAXN 205
#define MAXM 2005
#define INF 1000000

int T;
int in;
int cnt;
int f[MAXN][MAXM];
int siz[MAXN];

void DP(int &x) {
	int t, num;
	x = ++cnt;
	scanf("%d%d", &t, &num);
	if(num) {
		for(int i = 1; i <= num; i ++)
			f[x][i] = i * 5 + t * 2;
		siz[x] = num;
	} else {
		int L, R;
		DP(L);
		DP(R);
		siz[x] = siz[L] + siz[R];
		for(int i = 1; i <= siz[x]; i ++) {
			for(int j = 0; j <= i; j ++)
				if(f[L][j] != INF && f[R][i - j] != INF)
					f[x][i] = min(f[x][i], f[L][j] + f[R][i - j]);
			f[x][i] += t * 2;
			//cout<<x<<" "<<i<<" "<<f[x][i]<<endl;
		}	
	}
}

int main() {
	for(int i = 0; i < MAXN; i ++)
		for(int j = 1; j < MAXM; j ++)
			f[i][j] = INF;
	scanf("%d", &T);
	DP(in);
	int ans;
	for(int i = 0; i < MAXM; i ++)
		if(f[in][i] <= T)
			ans = max(ans, i);
	printf("%d", ans);
	return 0;
}

树形DP,f[i][j]表示结点i拿j幅画最少的时间。 是我方法错了吗?但是下载的数据都能过,在线就是过不了。

2022/3/9 21:52
加载中...