首页 > 代码库 > bzoj 1222 DP

bzoj 1222 DP

2024-07-03 12:59:31   228人阅读

　　用w[i]表示在A中用了i的时间时在B中最少用多长时间，然后转移就可以了。

　　备注：这个边界不好定义，所以可以每次用一个cur来存储最优值，然后对w[i]赋值就可以了。

/**************************************************************
    Problem: 1222
    User: BLADEVIL
    Language: C++
    Result: Accepted
    Time:2648 ms
    Memory:992 kb
****************************************************************/
 
//By BLADEVIL
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 6010
#define inf (~0U>>2)
 
using namespace std;
 
int n,m;
int a[maxn],b[maxn],c[maxn];
int w[maxn*5];
 
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for (int i=1;i<=n;i++) {
        if (!a[i]) a[i]=inf;
        if (!b[i]) b[i]=inf;
        if (!c[i]) c[i]=inf;
        m+=min(a[i],min(b[i],c[i]));
    }
    for (int i=1;i<=n;i++)
        for (int j=m;j>=0;j--) {
            int cur(inf);
            if (b[i]!=inf) cur=w[j]+b[i];
            if (j>=a[i]) cur=min(cur,w[j-a[i]]);
            if (j>=c[i]) cur=min(cur,w[j-c[i]]+c[i]);
            w[j]=cur;
        }
    int ans(inf);
    for (int i=1;i<=m;i++) ans=min(ans,max(i,w[i]));//printf("%d ",w[i]);
    printf("%d\n",ans);
    return 0;
}

 update：又仔细想了想这道题，发现其实是可以不用cur的，我们只需要每次假设当前i这个物品在某个机器上加工了，然后再不断更新就可以了。不知道哪里可能会溢出，所以将inf的值改小就可以了。

/**************************************************************
    Problem: 1222
    User: BLADEVIL
    Language: C++
    Result: Accepted
    Time:2100 ms
    Memory:992 kb
****************************************************************/
 
//By BLADEVIL
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 6010
#define inf (30010)
 
using namespace std;
 
int n,m;
int a[maxn],b[maxn],c[maxn];
int w[maxn*5];
 
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for (int i=1;i<=n;i++) {
        if (!a[i]) a[i]=inf;
        if (!b[i]) b[i]=inf;
        if (!c[i]) c[i]=inf;
        m+=min(a[i],min(b[i],c[i]));
    }
    for (int i=1;i<=n;i++)
        for (int j=m;j>=0;j--) {
            w[j]=w[j]+b[i];
            if (j>=a[i]) w[j]=min(w[j],w[j-a[i]]);
            if (j>=c[i]) w[j]=min(w[j],w[j-c[i]]+c[i]);
        }
    int ans(inf);
    for (int i=1;i<=m;i++) ans=min(ans,max(i,w[i]));//printf("%d ",w[i]);
    printf("%d\n",ans);
    return 0;
}

 


联系
我们