刷题记录(NC50959 To the Max,NC236172 货船,NC16655 [NOIP2005]过河)
NC50959 To the Max
题目链接
关键点:
1、题目要求求出二维数组里矩形的最大值,首先我们可以想到的是枚举矩形的左上角、右上角的端点,用二维数组前缀和可以减少计算。
对于前缀和sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
然后对于左上角(i, j),右下角(k1, k2),该区间的和为
ans = max(ans, sum[k1][k2]-sum[i-1][k2]-sum[k1][j-1]+sum[i-1][j-1]);
完整代码:
# include <bits/stdc++.h>
using namespace std;
int n;
int g[110][110];
int sum[110][110];
int res = -300, last, ans;
int main()
{
cin>>n;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
cin>>g[i][j];
// g[i][j] += g[i-1][j];
}
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+g[i][j];
}
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
for (int k1=i; k1<=n; k1++)
{
for (int k2=j; k2<=n; k2++)
{
ans = max(ans, sum[k1][k2]-sum[i-1][k2]-sum[k1][j-1]+sum[i-1][j-1]);
}
}
}
}
cout<<ans<<endl;
// cout<<res<<endl;
return 0;
}
2、如果N很大,那么该方法就会超时,我们可以减少一层for循环,通过枚举选择的两行,在选出的两行中求该区间内连续的最大值,每次更新这个答案
3、首先我们要先算出每行的前缀和,当在选择的两行中遍历列时,对于之前的列是否要选上,我们可以每次用一个值记住上一次计算出来的先前列(选出的两行中)的最大值,如果是大于零的,那么我们是可以加上先前列的值。记住每次都要更新答案
完整代码:
# include <bits/stdc++.h>
using namespace std;
int n;
int g[110][110];
int res = -300, last;
int main()
{
cin>>n;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
cin>>g[i][j];
g[i][j] += g[i-1][j];
}
}
for (int i=1; i<=n; i++)
{
for (int j=i; j<=n; j++)
{
last = 0;
for (int k=1; k<=n; k++)
{
last = max(last, 0) + g[j][k]-g[i-1][k];
res = max(res, last);
}
}
}
cout<<res<<endl;
return 0;
}
NC236172 货船
题目链接
关键点:
1、该题第一眼看的想法是,用数组dp[i],表示载重量为i时的最大的装载重量,然后用两层循环,从数据可以看出,肯定会超时
2、想法没有问题,我们可以想办法减少循环,用bitset数组b,对于可以组成的装载量的位置上置为1,首先我们初始化将第0为置为1,因为装载量为0千克,是可以实现的。
3、之后循环一遍货物,每次在该b数组上将可以组成的装载量的位置置为1,我们可以采用或运算,对于已经组成的装载量,他就会一直存在,且会影响后序装载量
b = b|(b<<w[i]);
4、最后我们从题目给出的最大装载量开始从大到小遍历b数组,有位置为1,那么该下标即为最大的装载量
完整代码:
# include <bits/stdc++.h>
using namespace std;
int n, a;
int w[100000+10];
int dp[100000+10];
bitset<100000+10>b;//表示第i千克是否能取到
int main()
{
cin>>n>>a;
for (int i=1; i<=n; i++)
cin>>w[i];
b.set(0, 1);
for (int i=1; i<=n; i++)
b = b|(b<<w[i]);
for (int i=a; i>=0; i--)
{
if (b[i])
{
cout<<i<<endl;
break;
}
}
return 0;
}
NC16655 [NOIP2005]过河
题目链接
关键点:
1、首先设dp[i],表示到达i距离,所跳的最少石头数,vis表示该点是否有石头(有为1,无为0)
dp[i] = min(dp[i-s]+vis[i], dp[i-s+1]+vis[i].....),很明显我们需要有两层循环,一层是遍历从起点到桥的距离,一层是遍历跳跃距离,很明显会超时
2、可以发现对于最后一个石头之后的位置对答案不产生影响,然后对于每个石头之间的距离,当石头之间的距离超过一定值时,我们是可以将其忽略,因为在这距离之后很有可能是重复之前的跳跃的方式,那么该值我们就取1-10的最小公倍数2050,在2050距离之后所有的距离都为先前跳跃的重复,我们可以将该距离对2050取余,这样一来就大大减少了最后一个石头的距离,不会超过10^6;
3、然后我们就可以开始用该距离开始遍历,最后的答案就从这个最后一个石头的距离到该距离+最长步数里面再取最小值
4、这里还有一特判,对于最小步数和最长步数相同的情况,我们可以直接看石头为该步数的倍数的数量,即为答案
完整代码:
# include <bits/stdc++.h>
using namespace std;
int l, s, t, m;
int vis[10000000];
int dp[10000000];
int a[100+10];
int dis[110];
int ans;
int main()
{
cin>>l>>s>>t>>m;
for (int i=1; i<=m; i++)
cin>>a[i];
sort(a+1, a+1+m);
if (s==t)
{
for (int i=1; i<=m; i++)
{
if (a[i]%t == 0)
ans++;
}
cout<<ans<<endl;
return 0;
}
for (int i=1; i<=m; i++)
{
dis[i] = (a[i]-a[i-1])%2050;
}
int len = 0;
for (int i=1; i<=m; i++)
{
len += dis[i];
vis[len] = 1;
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int i=1; i<=len+t; i++)
{
for (int j=s; j<=t; j++)
{
if (i-j>=0)
dp[i] = min(dp[i-j]+vis[i], dp[i]);
}
}
ans = 110;
for (int i=len; i<=len+t; i++)
ans = min(ans, dp[i]);
cout<<ans<<endl;
return 0;
}