1 条题解

  • 0
    @ 2023-9-20 9:21:36

    image

    #include <bits/stdc++.h>
    #define ll long long
    #define mod 998244353
    using namespace std;
    const int N=205;
    int n,m,k,s,t,L,SUM[N];
    int f[N][N][N][2];//f[i][j][k] 左边走了i步,右边走了j步,拿到k个雕像,最少时间 
    struct node{
    	int x,t;
    }a[N];
    void cmin(int &a,int b){
    	a=min(a,b);
    }
    int main(){  
    //	freopen("in.txt","r",stdin);
    	cin>>n>>L;
    	memset(f,0x3f,sizeof(f));
    	f[0][0][0][0]=0; 
    	for (int i=1;i<=n;++i) cin>>a[i].x;
    	for (int i=1;i<=n;++i) cin>>a[i].t;
    	for (int i=1;i<=n;++i) SUM[i]=L-a[n-i+1].x;
    	for (int i=0;i<=n;++i)
    		for (int j=0;i+j<n;++j)
    			for (int k=0;k<=i+j;++k){
    				if (f[i][j][k][0]<0x3f3f3f3f){
    					cmin(f[i+1][j][k+(f[i][j][k][0]+a[i+1].x-a[i].x<=a[i+1].t)][0],f[i][j][k][0]+a[i+1].x-a[i].x);
    					cmin(f[i][j+1][k+(f[i][j][k][0]+a[i].x+SUM[j+1]<=a[n-j].t)][1],f[i][j][k][0]+a[i].x+SUM[j+1]);
    				}
    				if (f[i][j][k][1]<0x3f3f3f3f){
    					cmin(f[i][j+1][k+(f[i][j][k][1]+a[n-j+1].x-a[n-j].x<=a[n-j].t)][1],f[i][j][k][1]+a[n-j+1].x-a[n-j].x);
    					cmin(f[i+1][j][k+(f[i][j][k][1]+SUM[j]+a[i+1].x<=a[i+1].t)][0],f[i][j][k][1]+SUM[j]+a[i+1].x);
    				}
    			}
    	int ans=0;
    	for (int i=0;i<=n;++i)
    		for (int k=0;k<=n;++k)
    			if (f[i][n-i][k][0]<0x3f3f3f3f || f[i][n-i][k][1]<0x3f3f3f3f)
    				ans=max(ans,k);
    	cout<<ans;
    }
    
    • 1

    [JOI 2020 Final] スタンプラリー 3

    信息

    ID
    497
    时间
    2000ms
    内存
    1024MiB
    难度
    3
    标签
    递交数
    38
    已通过
    22
    上传者