刷题记录（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 
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<
//     cout<
    
    return 0;
}

2、如果N很大，那么该方法就会超时，我们可以减少一层for循环，通过枚举选择的两行，在选出的两行中求该区间内连续的最大值，每次更新这个答案

3、首先我们要先算出每行的前缀和，当在选择的两行中遍历列时，对于之前的列是否要选上，我们可以每次用一个值记住上一次计算出来的先前列（选出的两行中）的最大值，如果是大于零的，那么我们是可以加上先前列的值。记住每次都要更新答案

完整代码：

# include 
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<
    
    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 
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<
    for (int i=a; i>=0; i--)
    {
        if (b[i])
        {
            cout<
            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 
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<
        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<
    
    return 0;
}