题解 - Vijos

1

#include <cstdio>
#define maxn 500
using namespace std;

int a[maxn],b[maxn],f[maxn][maxn];
int n,m;

int main()
{
    scanf("%d%d",&m,&n);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            f[i][j]=12345678;
    for (int i=1;i<=n;i++)
    {
        int t1,t2;
        t1=t2=0;
        for (int j=1;j<=i;j++)
        {
            t1+=a[i-j+1];
            t2+=b[i-j+1];
            if (t1>m||t2>m) 
            {
                break;
            }
            if (i==j) 
            {
                f[i][j]=3;
                break;
            }
            int t3=t1;
            for (int k=1;k<=i-j;k++)
            {
                t3+=b[i-j-k+1];
                if (t3>m) f[i][j]=f[i][j]<f[i-j][k]+2?f[i][j]:f[i-j][k]+2;
                     else f[i][j]=f[i][j]<f[i-j][k]+1?f[i][j]:f[i-j][k]+1;
            }
        }
    }
    int ans=12345678;
    for (int i=1;i<=n;i++)
        ans=ans<f[n][i]?ans:f[n][i];
    printf("%d",ans);
}

1

181818181818 LV 10 @ 16 年前

由于做题是有序的，所以就有了阶段，我们用f[k,i]表示前k天完成前i道题的最小欠费，方程为f[k,i]:=min{sum_b[j+1,i]|sum_a[j+1,i]+f[k-1,j]

0

Sky1231 (sky1231) LV 10 @ 7 年前

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,ans;
int a[301];
int b[301];
int f[1001][301];

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        for (int i=1;i<=m;i++)
            scanf("%d%d",&a[i],&b[i]);
        memset(f,oo_min,sizeof(f));
        for (ans=2,f[ans][0]=n;f[ans][m]<=oo_min;ans++)
            for (int i=m;i>=0;i--)
                if (f[ans][i]>oo_min)
                {
                    f[ans+1][i]=n;
                    for (int cnt=i+1,temp_1=f[ans][i],temp_2=n;temp_1>=a[cnt]&&temp_2>=b[cnt];cnt++)
                    {
                        temp_1-=a[cnt];
                        temp_2-=b[cnt];
                        f[ans+1][cnt]=max(f[ans+1][cnt],temp_2);
                    }
                }
        printf("%d\n",ans);
    }
}

sky1231 @ 7 年前

很H2O的题

0

li7777742 LV 10 @ 15 年前

Flag 　　Accepted

题号　　P1322

类型(?) 　　动态规划

通过　　357人

提交　　1286次

通过率　　28%

难度　　2

不用动态规划用宽搜+hash

好

program ss;

var

b:array [1..1000,1..2] of longint;

a:array [1..1000000,1..3] of longint;

c:array [1..1000,1..1000] of longint;

m,p,i,j,q,w,e,r:longint;

begin

readln(m,p);

for i:=1 to p do

readln(b,b);

a[1,1]:=1;

a[1,2]:=0;

a[1,3]:=0;

i:=1;

j:=1;c[0,0]:=1;

while a=0) and (w>=0) do

begin

if c[e,w]=0 then begin

inc(j);c[e,w]:=1;

a[j,3]:=w;

a[j,2]:=e;

a[j,1]:=a+1;

if e=p then begin writeln(a[j,1]);halt;end;

end;

inc(e);dec(q,b[e,1]);dec(w,b[e,2]);

end;

inc(i);

end; r:=i;

writeln(a[r,1]);

end.

半度微凉 @ 10 年前

求完整的代码！！！

0

zhh1993 LV 10 @ 15 年前

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

悲剧了，交上去莫名其妙编译不通过....

第一个月没钱，所以一定要工作，最后要加1.....

0

darin LV 10 @ 15 年前

orz

我是从后往前dp的额，，，，总感觉从前往后dp，，，还影响后面的，，哎，，太弱了想不通。。。。。。。

0

fp_cxs LV 9 @ 15 年前

注意题目！！！！！！！！！！！！！！！！！！！！！！！！！！！

0

麟弦 LV 9 @ 15 年前

whyvine的解题报告：

http://blog.sina.com.cn/s/blog_618b6ea70100elgo.html

0

陈亮宇 LV 10 @ 15 年前

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

不知道原因。。我用集装箱问题一样的方法过了。。

感谢 cheesecow 的解释！

0

library LV 8 @ 15 年前

我用P1306的方程略加补充。。。。过了。。。

0

zhanghanyuan LV 10 @ 15 年前

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

过了，O（N2）似乎也可以过

0

cheesecow LV 8 @ 15 年前

为什么要加一呢，因为第一个月没有启动资金，什么也不能做

0

xiaoX LV 10 @ 16 年前

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

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

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

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

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

没考虑到边界问题，把数组开 301 就过了…… 不然 WA 8、9

貌似我用的方法和大家题解不一样啊：

首先不是什么高效的算法—— O（N^3）

状态描述：F表示已开始第 i 个任务，已完成第j 个任务所需要的最小月数；初始化为正无穷大， F[0,0]=0;

解： F[n，n]+1 至于为什么要加一，我是没搞懂 …… 我测样例就比答案少 1 ……

预处理 a表示第i到j任务启动资金和

b……………… 结束……

for i:=0 to n do

for j:=0 to n do f:=700;

f[0,0]:=0;

for i:=1 to n do

for j:=0 to i do

for k:=0 to j do

if b[k+1,j]+a[j+1,i]f[j,k]+1 then

f:=f[j,k]+1;

writeln(f[n,n]+1);

半度微凉 @ 10 年前

请问预处理的b是干什么的。。求预处理的代码

0

panzer_wy LV 10 @ 16 年前

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

这题为什么数组开大点就过去了呢…………#&￥*（%@%#@

0

luyifan LV 10 @ 16 年前

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

铁筛菜 LV 8 @ 16 年前

ans=min+1

0

zhh LV 4 @ 16 年前

f表示做完前i题欠费j元的最小月数;

f=min{f[k,sum(t[k+1],t[i])]}+1 其中 sum(t[k+1],t[i])

0

190235047 LV 3 @ 16 年前

在别人帮助下终于把这个题AC了

但还是郁闷的很···

0

zsy90943 LV 10 @ 16 年前

果然猥琐....前一个程序看上去像DP...实质是贪心..心寒啊#15.后来自己搞了个测试数据..错掉- -！！F[L，X]表示第L个月，做了第X道题下个月要付的钱。发现反正这个F[L，X]一定要搜到头，找到最小值，不能在中间的时候找不到就退出搜索。如果在中间找不到就退出，那是贪心- -！！不是DP....完全不是一个档次~挖哈哈

0

fjxmlhx LV 10 @ 16 年前

ans=最小答案+2

题解

43 条题解

解题

信息

状态

开发

支持

题解

43 条题解

解题

信息

状态

开发

支持

还没有账户？

登录