1 条题解
-
0
#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
信息
- ID
- 497
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 3
- 标签
- 递交数
- 38
- 已通过
- 22
- 上传者