简要题面
给定 和数组 ，求 个长度为 的数组 ，使得：
- 对于 ，。
- 。
求以下式子的最大值。
测试点
直接 暴力枚举数组 ，判断是否满足上面 个式子，求解答案即可。
时间复杂度 ，空间复杂度 。
代码如下：
#include<bits/stdc++.h>
#define int long long
#define ll unsigned long long
#define off ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pi pair<int,int>
#define pii pair<int,pair<int,int> >
using namespace std;
const int N=305;
int n,m,T,X,t,a[N][N],cnt[N][N],ans;
void dfs(int step,int lt,int e,int sum)
{
if(step>m)
{
if(e>=0)
{
ans=max(ans,sum);
}
return;
}
for(int i=1;i<=n;i++)
{
dfs(step+1,i,e-abs(lt-i),sum+cnt[step][i]);
}
}
signed main()
{
off;
cin>>t;
while(t--)
{
cin>>n>>m>>X>>T;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
memset(cnt,0,sizeof(cnt));
ans=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=max((int)(1),j-X);k<=min(n,j+X);k++)
{
cnt[i][j]+=a[i][k];
}
}
}
for(int i=1;i<=n;i++)
{
dfs(2,i,T,cnt[1][i]);
}
cout<<ans<<'\n';
}
return 0;
}
测试点
考虑 dp， 表示是现在考虑到了第 行，，共计花费 的体力。
转移则是再枚举 维 ，表示 的值。
则转移方程可表示为：
不难发现， 的部分可以预处理出来，单独用一个数组存储。
时间复杂度 ，空间复杂度 。
代码如下：
#include<bits/stdc++.h>
#define int long long
#define ll unsigned long long
#define off ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pi pair<int,int>
#define pii pair<int,pair<int,int> >
using namespace std;
const int N=305;
int n,m,T,X,a[N][N],f[N][N][N],cnt[N][N],ans;
signed main()
{
off;
int c;
cin>>c;
while(c--)
{
cin>>n>>m>>X>>T;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
memset(f,0,sizeof(f));
memset(cnt,0,sizeof(cnt));
ans=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=max((int)(1),j-X);k<=min(n,j+X);k++)
{
cnt[i][j]+=a[i][k];
}
}
}
for(int i=1;i<=n;i++)
{
f[1][i][0]=cnt[1][i];
}
for(int i=2;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
for(int e=0;e<=T;e++)
{
for(int k=1;k<=n;k++)
{
// f[i-1][k][e]->f[i][j][e+abs(k-j)]
if(e+abs(k-j)>T)
{
continue;
}
f[i][j][e+abs(k-j)]=max(f[i][j][e+abs(k-j)],f[i-1][k][e]+cnt[i][j]);
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=T;j++)
{
ans=max(ans,f[m][i][j]);
}
}
cout<<ans<<'\n';
}
return 0;
}
测试点
，也就代表李老师会一直站在一个位置，换言之，。
枚举 的值，暴力计算答案即可。
时间复杂度 ，空间复杂度 。
代码如下：
#include<bits/stdc++.h>
//#define int long long
#define ll unsigned long long
#define off ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pi pair<int,int>
#define pii pair<int,pair<int,int> >
using namespace std;
const int N=305;
int n,m,T,X,a[N][N],ans;
signed main()
{
off;
int C;
cin>>C;
while(C--)
{
ans=0;
cin>>n>>m>>X>>T;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++)
{
int cnt=0;
for(int k=max((int)(1),i-X);k<=min(n,i+X);k++)
{
for(int j=1;j<=m;j++)
{
cnt+=a[j][k];
}
}
ans=max(ans,cnt);
}
cout<<ans<<'\n';
}
return 0;
}
测试点
特殊性质 A，以及 。
对于每一个时刻，都可以选择花费一定的代价去获得 点贡献。
设第 行 。
可以定义 dp 状态， 表示对于前 分钟，第 分钟获得这点贡献的且总共花费为 的最大答案。
转移时再枚举上 次获得贡献是什么时候，设为时刻 ，则转移为：
时间复杂度 ，空间复杂度 。
代码如下：
#include<bits/stdc++.h>
#define int long long
#define ll unsigned long long
#define off ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pi pair<int,int>
using namespace std;
const int N=305;
int c,n,m,X,T,q[N],f[N][N],ans;
signed main()
{
off;
cin>>c;
while(c--)
{
cin>>n>>m>>X>>T;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
int x;
cin>>x;
if(x)
{
q[i]=j;
}
}
}
memset(f,0,sizeof(f));
for(int i=1;i<=m;i++)
{
f[i][0]=1;
for(int j=1;j<i;j++)
{
for(int k=abs(q[i]-q[j]);k<=T;k++)
{
f[i][k]=max(f[i][k],f[j][k-abs(q[i]-q[j])]+1);
}
}
}
ans=0;
for(int j=1;j<=m;j++)
{
for(int i=0;i<=T;i++)
{
ans=max(ans,f[j][i]);
}
}
cout<<ans<<'\n';
}
return 0;
}
正解
延续测试点 的 dp 思路，观察到 的部分的复杂度可以进行优化。
先将转移拆解，对于每个点，它可以从上一次在它左侧和它右侧转移过来。
考虑从左侧转移的情况。
若在本行我们选择了第 个点，我们在上一行选择了第 个点，则我们要花费 的体力。
我们是不是可以换一下思路，如果上次我们选了第 个点，我们也可以考虑在这次前走到第 个点，花费 点体力。
那这样就好办了，我们定义 为第 行，决策完毕后，从左侧走到第 列，共计花费 的体力的最大答案。
则转移为：
指从 的位置走过来，花费 体力； 指这一行选择第 个点。
从右侧过来的同理可维护一个 数组。
这样我们会得到 份 的代码。
观察到， 个 在 的空间下是不够的，而答案又会超过 的范围，所以我们需要用滚动数组。
时间复杂度 ，空间复杂度 。
代码如下：
#include<bits/stdc++.h>
//#define int long long
#define ll unsigned long long
#define off ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pi pair<int,int>
#define pii pair<int,pair<int,int> >
using namespace std;
const int N=305;
int n,m,T,X,t,a[N][N],f[2][N][N],pre[N][N],suf[N][N],cnt[N][N],tmp[N],ans;
signed main()
{
off;
cin>>t;
while(t--)
{
cin>>n>>m>>X>>T;
memset(a,0,sizeof(a));
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
memset(f,0,sizeof(f));
memset(pre,0,sizeof(pre));
memset(suf,0,sizeof(suf));
memset(cnt,0,sizeof(cnt));
memset(tmp,0,sizeof(tmp));
ans=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=max((int)(1),j-X);k<=min(n,j+X);k++)
{
cnt[i][j]+=a[i][k];
}
}
}
for(int i=1;i<=n;i++)
{
f[1][i][0]=cnt[1][i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;i+j<=n;j++)
{
pre[i+j][j]=f[1][i][0];
}
}
for(int i=n;i>0;i--)
{
for(int j=0;i-j>0;j++)
{
suf[i-j][j]=f[1][i][0];
}
}
for(int i=2,op=0;i<=m;i++,op=1-op)
{
for(int j=1;j<=n;j++)
{
for(int k=0;k<=T;k++)
{
f[op][j][k]=max(pre[j][k],suf[j][k])+cnt[i][j];
}
}
memset(pre,0,sizeof(pre));
memset(suf,0,sizeof(suf));
memset(tmp,0,sizeof(tmp));
for(int j=1;j<=n;j++)
{
for(int k=T;k>0;k--)
{
tmp[k]=tmp[k-1];
}
tmp[0]=0;
for(int k=0;k<=T;k++)
{
tmp[k]=max(tmp[k],f[op][j][k]);
}
for(int k=0;k<=T;k++)
{
pre[j][k]=tmp[k];
}
}
memset(tmp,0,sizeof(tmp));
for(int j=n;j>0;j--)
{
for(int k=T;k>0;k--)
{
tmp[k]=tmp[k-1];
}
tmp[0]=0;
for(int k=0;k<=T;k++)
{
tmp[k]=max(tmp[k],f[op][j][k]);
}
for(int k=0;k<=T;k++)
{
suf[j][k]=tmp[k];
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=T;j++)
{
// cout<<i<<' '<<f[m%2][i][j]<<'\n';
ans=max(ans,f[m%2][i][j]);
}
}
cout<<ans<<'\n';
}
return 0;
}
暂无评论