无邪的飞行棋
Time Limit
1s
Memory Limit
64KB
Judge Program
Standard
Ratio(Solve/Submit)
15.38%(4/26)
Description:
大家还记得小时候玩过的飞行棋游戏吧，和小伙伴们一起体验飞行的乐趣！随着岁月的流逝我们换个方法重温这个游戏。 开始我们都在起点0，我们的目标是到达目的地M（0 < M < 1000）。现在我们手中有N(0 < N < 100)种点数，每种点数的大小为K(0 < k < 23)，这种点数的个数为C（0 < C < 100）个。我们使用一个大小为K的点数，我们就能前进K步。现在想知道，我们通过使用这些点数，能否到达目的地，如果不能输出“Naivete”，如果能到达目的地，输出我们到达目的地使用的点数最少的个数！注意我们没到达一步都要在0~M的范围内（如果你现在在M-2这个地方，如果使用8点，前进8步，超过M，是不允许的） Input:
输入有多组数据，每组数据： 第一行输入M，N。接写来的N行输入K，C； 输入以EOF结束 Output:
如果不能到达输出“Naivete”，如果能到达，输出我们能使用的点数的最少个数！ Sample Input:
11 4
3 3
1 11
5 2
6 3 22 3
2 4
1 7
3 2
Sample Output:
2
Naivete
这是一道一眼就可以看出来的经典背包问题，只是原来的背包问题是求最大价值
在这道题目里是求使用点数的最少个数，原理是一样的
01背包问题：一个背包总容量为V，现在有N个物品，第i个 物品体积为weight[i]，价值为value[i]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？ 动态规划先找出子问题，我们可以这样考虑：在物品比较少，背包容量比较小时怎么解决？ 用一个数组f[i][j]表示，在只有i个物品，容量为j的情况下背包问题的最优解， 那么当物品种类变大为i+1时，最优解是什么？第i+1个物品可以选择放进背包或者不放进背包（这也就是0和1）， 假设放进背包（前提是放得下） 那么f[i+1][j]=f[i][j-weight[i+1]+value[i+1]；如果不放进背包，那么f[i+1][j]=f[i][j]。 这就得出了状态转移方程： f[i+1][j]=max(f[i][j],f[i][j-weight[i+1]+value[i+1])。
内存优化，把二维背包降成一维，然后从后往前推即可
Conference: http://blog.****.net/kangroger/article/details/38864689
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
#define MOD 1000000007
#define pi acos(-1.0) using namespace std; typedef long long ll ;
typedef unsigned long long ull ;
typedef unsigned int uint ;
typedef unsigned char uchar ; template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}
template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;} const double eps = 1e- ;
const int N = ;
const int M = * ;
const ll P = 10000000097ll ;
const int MAXN = ;
const int INF = 0x3f3f3f3f ;
const int offset = ; int dp[];
int n, m, cur; int main() {
std::ios::sync_with_stdio(false);
int i, j, t, k, u, c, v, p, numCase = ; while (cin >> m >> n) {
memset (dp, 0x3f, sizeof(dp));
dp[] = ;
for (i = ; i < n ; ++i) {
cin >> c >> k;
for (j = ; j < k; ++j) {
for (cur = m; cur >= ; --cur) {
if (cur - c >= ) {
if (dp[cur - c] != INF) {
checkmin (dp[cur], dp[cur - c] + );
}
}
}
}
}
if (dp[m] == INF) {
printf("Naivete\n");
} else {
printf("%d\n",dp[m]);
}
} return ;
}