很委琐

而他希望其他的所有油井还能够像往常一样正常运输

是完全正常，不是部分正常

下面是原题解

想一想，任何一个方格的下方和右方都没有空缺的方格，最终会是一个什么样的图形呢？你会直观地想到，这个图形中间肯定不能有“洞”，而且边缘也不能有“陷进去”的地方。再具体一些，空缺的只能是左上角的方格。我们可以按照题目意思想到一个更明确的规则：最左上角的那一块必须去掉，以后只能选择上方和左方全都空出来的格子。

或许有人会因此想到一个很简单的贪心策略：每次选择可以去掉的格子中权值最小的一个。很遗憾，这个方法是错误的。有可能存在这样一种情况，即虽然选了这个值比较大的方格，但正因为选了它才能选到后面很多值非常小的格子。下面便是一个简单的例子：

8 9 1

8 8 8

如果要选出3个格子去掉，那么按照贪心策略，最小值为25；但显然存在值为18的更优的方案，即选择第一行的三个格子。

z

如果你能想到用这样一个词来描述剩下的方格组成的形状，你应该立即想到动态规划的处理方法：按规则去掉这些格子后，剩下的一定呈“阶梯状”。

也就是说，每一行只能去掉左端的若干个格子，且去掉的格子数目不能超过上一行去掉的格子数。

我们用f表示前i行共去掉k个格子，且第i行去掉j个时的最优值，则f=Min{ f(t>=j) }+Sum，其中Sum表示第i行前j个格子的权值和，它可以在O(mn)的时间内预处理完成。这样，状态共O(mnk)，决策有O(n)种，由于k可以达到mn，因此总的复杂度为O(m^2*n^3)。这样的时间复杂度有一点高，可能不能通过极限数据。

看一看状态转移方程式，有优化的余地吗？我们发现，在寻找f的最小值时，我们花费了一些时间做了重复的工作。事实上，我们完全不需要每次都去寻找这个最小值，从而把决策降到O(1)。我们用一个O(nk)的附加空间建立数组min[j,k]表示在上一个阶段中，对于所有的t>=j，f的最小值是多少。这个工作可以在每次i增加前用O(nk)的时间完成，因为对于每个k，我们只需要从后往前扫描一遍数组f并不断更新最小值。总的复杂度被将为O(m^2*n^2)，完全可以通过所有的数据。这也是标程的算法。

总体思路和上面的ipip2005同学差不多，可是他的题解我并不能
完全看懂……（时间久远）这个就作为一个补充吧。

#include<bits/stdc++.h>
using namespace std;
class Ga {
private:
    int m, n, k, oil[62][62],f[62][3666][62],tot,fr[62][62];
    void init() {
        tot = 0;
        ios::sync_with_stdio(false);
        cin >> m >> n >> k;
        memset(f, 127, sizeof(f));
        memset(fr, 0, sizeof(fr));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                cin >> oil[i][j];
                fr[i][j] =fr[i][j-1]+ oil[i][j];//其实直接拿oil做前缀和就可以了，懒得改……
            }
        for (int i = 1; i <= m; i++)
            f[1][i][i] = fr[1][i];
    }
    int search(int i, int j,int be);
    void DP() {
        for (int i = 2; i <= n; i++)//设f[i][p][j]为第i行贡献前j个，当前总共贡献p个
            for (int p = 1; p <= min(k,i*m); p++)
                for (int j = 0; j <= min(m,p/i); j++)//因为呈阶梯状，故i行取最多时每行取的数量都相等，为p/i
                    if(p>j)
                    f[i][p][j] =search(i-1,p-j,j) + fr[i][j];
    }
public:
    void out() {
        ios::sync_with_stdio(false);
        init();
        DP();
        cout << search(n, k,0);
    }
}x;
int Ga::search(int i, int j,int be) {//因为前一行取的一定大于等于本行，所以从j开始向后找最小
    int ans = 2147483633;
    for (int p = be; p <=min(m,j); p++)
        ans = min(ans, f[i][j][p]);
    return ans;
}
int main()
{
    x.out();
    return 0;
}

这题数据有7个60*60

找了半天错。。。。

Accepted

状态 耗时 内存占用

#1 Accepted 20ms 51.5MiB
#2 Accepted 17ms 51.5MiB
#3 Accepted 20ms 51.504MiB
#4 Accepted 173ms 51.488MiB
#5 Accepted 120ms 51.492MiB
#6 Accepted 80ms 51.551MiB
#7 Accepted 137ms 51.5MiB
#8 Accepted 186ms 51.5MiB
#9 Accepted 162ms 51.5MiB
#10 Accepted 107ms 51.602MiB
代码

#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;
int a[61][61],f[61][3610][61],m,n,k,ans;
int main()
{
    cin>>m>>n>>k;
    memset(f,127,sizeof(f));
    ans=2147483647;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
                a[i][j]+=a[i][j-1];
            }
    for(int i=0;i<=m;i++)
        f[1][i][i]=a[1][i];
    for(int i=2;i<=n;i++)
        for(int j=0;j<=min(k,i*m);j++)
            for(int t=0;t<=min(k,min(m,j/i));t++)
                for(int l=t;l<=min(k,min(m,(j-t)/(i-1)));l++)
                    if(j>l)
                        f[i][j][t]=min(f[i-1][j-t][l]+a[i][t],f[i][j][t]);
    for(int i=0;i<=n;i++)
        ans=min(ans,f[n][k][i]);
    cout<<ans;
    return 0;
}

int m,n,ge,a[61][61],p[61][61],f[61][3610][61];
int sum(int i,int j)
{
int sumn=0;
for(int k=1;k<=j;k++)
sumn=sumn+a[i][k];
return sumn;
}
void chushi(int m,int n)
{
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
p[i][j]=sum(i,j);
}

int main()
{
cin>>n>>m>>ge;
memset(f,127,sizeof(f));
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
chushi(m,n);
for(int i=1;i<=n;i++)
f[1][i][i]=p[1][i];
for(int i=2;i<=m;i++)
for(int j=2;j<=min(ge,i*n);j++)
for(int t=1;t<=n;t++)
for(int l=t;l<=n;l++)
if(j>t)
f[i][j][t]=min(f[i-1][j-t][l]+p[i][t],f[i][j][t]);
int out=999999999;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
out=min(out,f[i][ge][j]);
cout<<out;

return 0;
}

我的dp效率比较低,所以我想了一个不是办法的办法:如果k比较小,就从左上角取;如果k比较大,就从右下角取(此时是选取留下来的油井).这样我用了两个结构很相似的dp才AC的(会不会很菜~~~~-_-!!?).

细节啊QwQ，100和0的差距

├ 测试数据 01：答案正确... (0ms, 52144KB)

├ 测试数据 02：答案正确... (26ms, 52144KB)

├ 测试数据 03：答案正确... (10ms, 52144KB)

├ 测试数据 04：答案正确... (69ms, 52144KB)

├ 测试数据 05：答案正确... (89ms, 52144KB)

├ 测试数据 06：答案正确... (89ms, 52144KB)

├ 测试数据 07：答案正确... (135ms, 52144KB)

├ 测试数据 08：答案正确... (0ms, 52144KB)

├ 测试数据 09：答案正确... (57ms, 52144KB)

├ 测试数据 10：答案正确... (135ms, 52144KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 614ms / 52144KB

可惜空间大了点

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 619ms

├ 测试数据 05：答案正确... 416ms

├ 测试数据 06：答案正确... 259ms

├ 测试数据 07：答案正确... 478ms

├ 测试数据 08：答案正确... 681ms

├ 测试数据 09：答案正确... 525ms

├ 测试数据 10：答案正确... 400ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3378ms

时间很丑

不知道那个啥测评器

总归 一次AC 很行

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 25ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 41ms

├ 测试数据 08：答案正确... 119ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：354ms

。。。。。 非要开滚动

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 134ms

├ 测试数据 05：答案正确... 72ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 56ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：581ms

时间真难看。。

预处理真麻烦。。。还很容易错。。

水题水题

这题细节可真不少……

怎么做lxx已经说得很详细了……

细心！

在程序中加了2个字符，居然就从20分升到100分...

郁闷了交了N回.

最后发现一个细节写错了..

午夜解决难题.

第6个点超时。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 228ms

├ 测试数据 05：答案正确... 103ms

├ 测试数据 06：答案正确... 72ms

├ 测试数据 07：答案正确... 134ms

├ 测试数据 08：答案正确... 275ms

├ 测试数据 09：答案正确... 228ms

├ 测试数据 10：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1159ms

dp题，空间和时间都可以优化。

详见oibh第一次模拟赛解题报告。

哪位大牛会做，指点一下，感激不尽啊！^-^