C，D一起 01背包问题
C：HDU - 2602
D : HDU - 2546
理解01背包递归公式，dp（k,V)=max(dp(k-1,V),dp(k-1,V-v[i])+v[i])...
C，D一起 01背包问题
C：HDU - 2602
D : HDU - 2546
理解01背包递归公式，dp（k,V)=max(dp(k-1,V),dp(k-1,V-v[i])+v[i])
看一下AC过的C的代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int w[N], v[N], dp[N];
int main()
{
int T;
cin >> T;
while (T--)
{
//for (int i = 0; i < N; i++)
//{
// dp[i] = 0;
//}
memset(dp, 0, sizeof(dp));//这里是按位归0，上面是int位归零一次
int n, V;
cin >> n >> V;
for (int i = 1; i <= n; i++)
{
cin >> v[i];//va
}
for (int i = 1; i <= n; i++)
{
cin >> w[i];//vo
}
for (int i = 1; i <= n; i++)
{
for (int j = V; j >= w[i]; j--)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[V] << endl;
}
}
后面V代入体积，w[]为单个体积，v[]为单个价值，理解不了可以套进去。
对比D的代码
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
int v[1051] ;
int s[1051] ;
int main()
{
while (cin >> n&&n)
{
memset(s, 0, sizeof(s));
for (int i = 1; i <= n; i++)
{
cin >> v[i];
}
sort(v + 1, v + n+1);
cin >> m;//钱
if (m < 5)cout << m << endl;
else {
int w/*记体积*/ = m - 5;
for (int i = 1; i < n; i++)
{
for (int j=/*背包体积*/w ;j>=/*最小体积*/ v[i] ;j--)
{
s[j] = max(s[j], (s[j - v[i]] + v[i]));
}
}
cout << m-s[w]-v[n] << endl;
}
}
}
在这里区别就是最大体积要忽略一开始的最大的5块钱，因为这五块钱可以溢出，减了5块之后就可以按照01背包做了，结果把情况弄清楚就行
F problem/HDU-1019
最小公倍数求法
先从欧几里得算法（辗转相除法）开始求出最大公因数
欧几里得算法
两个数中用小数去%大数，即假设a>b,r=a%b
让a=b，b=r，做一个循环，直至b==0时a就是最大公因子
最小公倍数求法
可以由最小公倍数*最大公因子=两数积求得
问题分析
这里有一个对于我来说是坑的地方，就是后面备注那个
上AC代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int p[N] = { 0 };
int ou(int a/*大*/, int b)
{
while (b != 0)
{
int r = a % b;
a = b;
b = r;
}
return a;
}
int main()
{
int T;
cin >> T;
while (T--)
{
int m;
cin >> m;
memset(p, 0, sizeof(p));
for (int i = 0; i < m; i++)
{
cin >> p[i];
}
sort(p, p + m);
for (int i = 0; i < m-1; i++)//让后一个成为最小公倍数
{
/*int x = p[i] * p[i + 1];
int y = ou(p[i + 1], p[i]);
p[i + 1] = x / y;*/
//p[i + 1] =( p[i]*p[i + 1] )/ (ou(p[i + 1], p[i]));这里看着没问题不过a，b同时很大会导致溢出int的范围
p[i + 1] = p[i] / (ou(p[i + 1], p[i]))*p[i + 1];
}
cout << p[m - 1] << endl;
}
}
注意那一点就ok
G /HDU-1061
可以用快速幂，不过有规律也能干掉他，这里用的是规律
直接代码
#include<iostream>
#include<cmath>
using namespace std;
//TLE
int main()
{
int T;
cin>> T ;
for (int i = 0; i < T; i++)
{
int N;
cin >> N;
int s = N % 10;
if (s == 0 || s == 1 || s == 5 || s == 6)cout << s << endl;
if (s==2)
{
int a = N % 4;
if (a == 0)cout << \"6\" << endl;
if (a == 1)cout << \"2\" << endl;
if (a == 2)cout << \"4\" << endl;
if (a == 3)cout << \"8\" << endl;
}
if (s==3)
{
int a = N % 4;
if (a == 0)cout << \"1\" << endl;
if (a == 1)cout << \"3\" << endl;
if (a == 2)cout << \"6\" << endl;
if (a == 3)cout << \"7\" << endl;
}
if (s==7)
{
int a = N % 4;
if (a == 0)cout << \"1\" << endl;
if (a == 1)cout << \"7\" << endl;
if (a == 2)cout << \"9\" << endl;
if (a == 3)cout << \"3\" << endl;
}
if (s==8)
{
int a = N % 4;
if (a == 0)cout << \"6\" << endl;
if (a == 1)cout << \"8\" << endl;
if (a == 2)cout << \"4\" << endl;
if (a == 3)cout << \"2\" << endl;
}
if (s==4)
{
int a = N % 2;
if (a == 0)cout << \"6\" << endl;
if (a == 1)cout << \"4\" << endl;
}
if (s==9)
{
int a = N % 2;
if (a == 0)cout << \"1\" << endl;
if (a == 1)cout << \"9\" << endl;
}
}
}
由于时间限制所以用循环做会TLE
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
