所以这题正解是什么
查看原帖
所以这题正解是什么
690333
qinghaipeng楼主2023/10/17 13:42
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<memory.h>
#include<cstdlib>
#include<ctime>
#include<climits>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<bitset>
#include<map>
#include<unordered_map>
#include<stack>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<utility>
//#include<Windows.h>
#define bug puts("liupei")
#define int long long
#define F(i,j,n) for(register int i=j;i<=n;++i)
#define R(i,j,n) for(register int i=j;i>=n;--i)
#define MAX_TIME 0.95
#define pii pair<int,int>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
const int N = 5e5+50;
int n, q, m, r;
int a[N], b[N], c[N], s1[N], s2[N];
int dp[N]; 
bool d[N];
bool p[N];
//初始序列为 1 
//1:全 0
//2:单 0
//3: 单 1 
//dp[i] 表示 1~i 最小代价 
//s1 表示 1~i 所有1变为0的最小代价
//s1 表示 1~i 所有0变为1的最大代价
signed main(){
	scanf("%lld", &n);
	F(i,1,n)scanf("%lld", &a[i]);
	F(i,1,n)scanf("%lld", &b[i]);
	F(i,1,n)scanf("%lld", &c[i]);
	scanf("%lld", &q);
	while(q--){
		F(i,1,n) p[i] = 0, s1[i] = 0, s2[i] = 0;
		scanf("%lld", &m);
		F(i,1,m){
			int x;
			scanf("%lld", &x);
			p[x]=1; 
		}
		F(i,1,n){
			//i~j把所有0变成 1就是 s1[j] - s2[i-1] 
			if(!p[i])s1[i]=b[i]; //累计1~i要把所有 1变成 0的代价 
			else s2[i]=c[i];//累计1~i要把所有0变成1的代价 
			s1[i]+=s1[i-1];//往后退 
			s2[i]+=s2[i-1];
		}
		F(i,1,n){
			//对于 1~i 的决策,有两种 
			//如果这个点要保留为 1,那么它要么不动,要么全部赋为0的时候再赋为1
			//如果这个点要变成 0,要么单点修改掉它,要么全部赋为0 
			if(p[i]) dp[i] = min(a[i] + s2[i], dp[i-1]);
			else dp[i] = min(dp[i-1]+b[i], a[i]+s2[i]); //全部赋为0,将之前的1加起来 
			dp[i] = min(dp[i], s1[i]); //全部都单点修改为0 
		}
		printf("%lld\n", dp[n]);
	}
	return 0;
}

Θ(q×n)\Theta(q\times n) 的DP 肯定过不了。

2023/10/17 13:42
加载中...