SDUT 2021 summer team contest 5th

A

题意

给你n个人每个人有一个区间然后再给你那个人必须在那个人前面，最后让你找出一个合法方案

分析

代码

#include
#define fnq freopen("input.txt","r",stdin)
using namespace std;
typedef long long ll;
typedef pairpii;
const int N=3e5+5,M=1e6+5;
struct Edge{int to,nex;}edge[M];int head[N],tot;
inline void add(int from,int to){edge[++tot]=(Edge){to,head[from]},head[from]=tot;}
int n,m;
queueq;int in[N],a[N],b[N],l[N],r[N];
int TOPO(){
    int num=0;
    for(int i=1;i<=n;++i) if(!in[i]) q.push(i);
    while(!q.empty()){
        int x=q.front();a[++num]=x,q.pop();
        for(int i=head[x];i;i=edge[i].nex){
            int y=edge[i].to;
            if(!(--in[y])) q.push(y);
        }
    }
    return num==n;
}
vectorvec[N];
int get_span(){
    for(int i=1;i<=n;++i)
        for(int j=head[a[i]],x,y;j;j=edge[j].nex) x=a[i],y=edge[j].to,l[y]=max(l[y],l[x]+1);//到i的时候 a[1]--a[i]都已经被更新好了。
    for(int i=1;i<=n;++i) b[i]=a[n-i+1];
    for(int i=1;i<=n;++i)
        for(int j=head[b[i]],x,y;j;j=edge[j].nex) x=b[i],y=edge[j].to,r[x]=min(r[x],r[y]-1);//显然到x的时候 y已经更新好了
    for(int i=1;i<=n;++i){
        if(l[i]>r[i]) return 0;//可能这个更新的过程就可以看出来不合法 即l[i]>r[i]
        vec[l[i]].push_back(make_pair(r[i],i));
    }
    return 1;
}
priority_queue,greater >Q;
int ans[N];
int work(){
    int num=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j

D

题意

你可以选择一些灯亮，然后他的左边右边都会亮，你还可以有k次机会交换灯的位置，求最少消费

分析

代码

#include 
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const db EPS = 1e-9;
const int N = 250000+100;
using namespace std;

int n,K;
ll dp[N][10][10][3],w[N];

int main()
{
	scanf("%d%d",&n,&K);
	rep(i,1,n) scanf("%lld",&w[i]);
	memset(dp,0x3f,sizeof dp);
	dp[0][0][0][0] = 0; //第i个位置，欠了j个，还了k个
	rep(i,1,n)
		rep(j,0,K){
			rep(k,0,K){
				dp[i][j][k][0] = dp[i-1][j][k][2];
				if(k > 0) dp[i][j][k][0] = min(dp[i][j][k][0],dp[i-1][j][k-1][2]+w[i]);

				dp[i][j][k][1] = dp[i-1][j][k][0];
				if(k > 0) dp[i][j][k][1] = min(dp[i][j][k][1],dp[i-1][j][k-1][0]+w[i]);		
				
				rep(h,0,2)
					dp[i][j][k][2] = min(dp[i][j][k][2],dp[i-1][j][k][h]+w[i]);
				if(j > 0){
					rep(h,0,2)
						dp[i][j][k][2] = min(dp[i][j][k][2],dp[i-1][j-1][k][h]);
				}
			}
		}
	ll ans = 1e17;
	rep(i,0,K)
		ans = min(ans,min(dp[n][i][i][0],dp[n][i][i][2]));
	printf("%lld\n",ans);
	return 0;
}
VJ

相关

DP基础 0306（VJ）

标签