hdu1712 ACboy needs your help 分组背包

August 11, 2013
Hdu DP

最基础的分组背包~


#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 dp[102], a[102][102];
int main(void)
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin );
    #endif // ONLINE_JUDGE
    int n,m;
    while (~scanf("%d%d",&n,&m)&&(n||m))
    {
        for (int i=1;i<=n;++i)
        {
            for (int j=1;j<=m;++j) scanf("%d",&a[i][j]);
        }
        memset(dp,0,sizeof(dp));
        for (int i=1;i<=n;++i)
        {
            for (int v=m;v>=0;--v)
            {
                for (int j=1;j<=v;++j)
                {
                    dp[v]=max(dp[v],dp[v-j]+a[i][j]);
                }
            }
        }
        printf("%d\n",dp[m]);
    }
    return 0;
}

没什么可说的。1Y

comments powered by Disqus