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