90分WA最后一个点,求dalao指点
查看原帖
90分WA最后一个点,求dalao指点
594337
jack15924746094楼主2022/7/20 20:56
#include<bits/stdc++.h>
#define IOS	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl "\n"
#define ll long long
#define INF 0x3f
const ll N = 1e3 + 10;
using namespace std;
//素数判断 primejudge
//高精度 + - * /
//质因数分解 pf
map<ll, ll>num;
ll nn[N],tn[N], tp[N],sump[N];
ll dp[N][N][2], n,xo,sumy,cnt,c;
ll cal(ll tl, ll tr, ll pl, ll pr) { return (sump[cnt] - sump[pr] + sump[pl - 1]) * (nn[tr] - nn[tl]); }
int main()
{
	//IOS;
	scanf("%lld%lld", &n, &xo);
	num[xo] = 0;
	for (ll i = 1; i <= n; i++) { scanf("%lld", &tn[i]); }
	for (ll i = 1; i <= n; i++) {
		ll tmp;
		scanf("%lld", &tmp);
		sumy += tmp;
	}
	for (ll i = 1; i <= n; i++) { scanf("%lld", &tp[i]); }
	for (ll i = 1; i <= n; i++) { num[tn[i]] = tp[i];}
	cnt = 0,c;
	for (auto it = num.begin(); it != num.end(); it++) { 
		nn[++cnt] = it->first;
		if (it->first == xo) { c = cnt; }
	}
	for (ll i = 1; i <= cnt; i++) {sump[i] = sump[i - 1] + num[nn[i]];}
	for (ll i = 0; i <= 1; i++) {
		for (ll j = 1; j <= cnt; j++) {
			for (ll z = 1; z <= cnt; z++) {
				dp[j][z][i] = 1000000000;
			}
		}
	}
	dp[c][c][1] = dp[c][c][0] = 0;
	for (ll len = 2; len <= cnt; len++) {
		for (ll i = 1; i + len <= cnt + 1; i++) {
			ll j = i + len - 1;
			dp[i][j][1] = min(dp[i][j - 1][1] + cal(j - 1, j, i, j - 1), dp[i][j - 1][0] + cal(i, j, i, j - 1));
			dp[i][j][0] = min(dp[i + 1][j][0] + cal(i, i + 1, i + 1, j), dp[i + 1][j][1] + cal(i, j, i + 1, j));
		}
	}
	double tmp=sumy-min(dp[1][cnt][1],dp[1][cnt][0]);
	printf("%.3lf\n", tmp / 1000.0);
	return 0;
}

2022/7/20 20:56
加载中...