zoj3623 Battle Ships ——完全背包？简单DP！|| 泛化背包

August 15, 2013
ZOJ DP

link:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3623 看起来像完全背包，但是物品价值是变化的，所以很多人搞的很复杂。晚上的代码要么很复杂，有一个代码虽然很简洁在zoj可以过，但是是错误的。求教lyl神犇，果然思想很深刻，抓住乐问题的本质，想法比网上搜到的所有博客里面的做法都简洁。事实上，就是简单的DP，抓住一个技巧：让时间倒流，也就是说，把时间反过来考虑，先在将来把船造好，然后在过去用船攻击，哈哈，太巧秒了，说起来很别扭，很有意思，dp[j+time[i]]=max(dp[j]+j*time[i])；dp[j]表示在j这个时间，所造成的最大伤害。这样就可以枚举时间，在每个特定的时间内，枚举船的种类，找到最大值。最终在dp[]数组里面找到符合条件的并且时间最少的解。只能说，ORZ…… 后来好不容易想明白了。茶具从哪里来……


/*
ID: zypz4571
LANG: C++
TASK: battle.cpp
 */

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
using namespace std;
int Time[33],dam[33], f[444];
int main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    int n,l;
    while (~scanf("%d%d",&n,&l)){
        for (int i=1;i<=n;++i) scanf("%d%d",Time+i,dam+i);
        memset(f,0,sizeof(f)); f[0]=0;
        for (int j=0;j<=355;++j) {
            for (int i=1;i<=n;++i) {
                f[j+Time[i]]=max(f[j+Time[i]],f[j]+j*dam[i]);
            }
        }
        int ans=INF;
        for(int i=0;i<=355;++i) {
            if(f[i]>=l&&ans>i) ans=i;
        }
        printf("%d\n",ans);
    }
        return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */

学算法重在理解，思考，而不是套模板什么的。理解了就不用记忆了。比如这道题目，一看，就很想完全背包，然后就搞的很复杂的样子…… 其实，这道题目还有一个比较聪明的解法，因为时间最多只有300+，所以我们可以枚举时间，二分答案，对每个时间判断是否合法就ＯＫ，判断的时候，按照时间正序排就行，ｌｙｌ神犇给讲的，好吧，我不会写…… 做完这道题目觉得动态规划很有意思。

Read more