一.最大值问题
1.模板题
注意多组测试数据，需要将数组清零
2.最大报销额
数据处理较复杂。
首先，每张发票中不能有除了A、B、C以外的其他类型；
其次，每张发票中各个类型总和不超过600.如A:200.0 A:401.0，是无效的发票
先处理好发票后，剩下的01背包问题处理方式较多。
法一：f[i][j]表示前i张发票中报销了j张的最大数额
则f[i][j]=max(f[i-1][j], f[i-1][j-1]+v)，其中v是第i张发票的数额。
注意转移时要求f[i-1][j-1]+v<m，即金额不超过最大限度
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
double f[N];
double v[N];
int t;
double m;
int main(){
while(cin >> m >> t, t){
memset(f,0,sizeof f);
int n=0;
while(t--){
int num; cin >> num;
double price[]={0,0,0};
bool valid=true;
while(num--){
string s;
cin >> s;
double p = stod(s.substr(2));//string to double
if(s[0]=='A') price[0]+=p;
else if(s[0]=='B') price[1]+=p;
else if(s[0]=='C') price[2]+=p;
else valid=false;
}
double sum = price[0]+price[1]+price[2];
if(price[0]>600 || price[1]>600 || price[2]>600 || sum>1000) valid=false;
if(valid) v[n++]=sum;
}
for(int i=0;i<n;i++){
for(int j=i;j>=0;j--){
//f[i][j]表示前i张发票报销了j张的最大花费
if(f[j-1]+v[i]<=m)
f[j]=max(f[j], f[j-1]+v[i]);
}
}
double res=0;
for(int i=0;i<n;i++) res=max(res,f[i]);
printf("%.2lf\n",res);
}
return 0;
}
法二：f[i][j]表示前i张发票中，开销不超过j元的最大花费
则f[i][j]=max(f[i-1][j], f[i-1][j-v]+v)，其中v是第i张发票的花费
需要将小数乘100，化成整数处理
代码片段：
const int N = 35, M=3e6+5;
int f[M];
int v[N];
int maxn = (int)(m*100);
for(int i=0;i<n;i++){
for(int j=maxn;j>=v[i];j--){
if(f[j-v[i]]+v[i]<=maxn) //这一行可以省去，因为数归可证f[j]<=j
f[j]=max(f[j], f[j-v[i]]+v[i]);
}
}
printf("%.2lf\n",1.0*f[maxn]/100);
法三：f[i]表示从前i张发票中选，且包含第i张发票的最大报销额
则f[i]=max{f[j]+v[i]}，其中v[i]是第i张发票的价格，0<=j<=i-1
由于转移需要条件限制f[j]+v[i]<=m，因此无法用滑动窗口
const int N = 35;
double f[N];
double v[N];
for(int i=0;i<n;i++){
f[i]=v[i];
for(int j=0;j<i;j++){
if(f[j]+v[i]<=m){
f[i]=max(f[i],f[j]+v[i]);
}
}
}
double ans=0;
for(int j=0;j<n;j++) ans=max(ans,f[j]);
printf("%.2lf\n",ans);
3.Buy the souvenirs
给定每个物品的价格，问怎样买才能使获得物品个数最多，并求方案数。
转化思路：将每个物品价值视为1，求个数最大值即求总价值最大值和方案数。
f[i][j]表示前i个物品，花费不超过j的最大价值
g[i][j]表示前i个物品，花费不超过j达到最大价值的方案数
也可以将不超过改为恰好，只需修改初始化和最终求答案的部分即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 33, M = 505;
int a[N];
int n,m;
int f[M], g[M];
//f[i][j]表示前i个物品，花费不超过j的最大价值
//g[i][j]表示前i个物品，花费不超过j达到最大价值的方案数
int main(){
int T;
cin >> T;
while(T--){
memset(f,0,sizeof f);
cin >> n >> m;
for(int i=0;i<n;i++) cin >> a[i];
for(int i=0;i<=m;i++) g[i]=1;
for(int i=0;i<n;i++){
for(int j=m;j>=a[i];j--){
if(f[j-a[i]]+1==f[j]){
g[j]+=g[j-a[i]];
}
else if(f[j-a[i]]+1>f[j]){
f[j]=f[j-a[i]]+1;
g[j]=g[j-a[i]];
}
}
}
if(f[m]==0) puts("Sorry, you can't buy anything.");
else printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",g[m],f[m]);
}
return 0;
}
二.最小值问题
http://acm.hdu.edu.cn/showproblem.php?pid=1203
求至少收获一份offer的最大概率，反过来就是求所有offer都得不到的最小概率
在选出的学校中，所有offer都得不到的概率就是每个学校都得不到的概率乘积
用f[i][j]表示前i个学校，花费不超过j时收不到offer的最小概率
则状态转移方程f[i][j]=min(f[i-1][j], f[i-1][j-v]*p)
其中v是第i个学校的费用，p是第i个学校收不到offer的概率
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
double f[N];
int n, m;
int main(){
while(scanf("%d %d",&m,&n),n||m){
for(int i=0;i<=m;i++) f[i]=1;
int v;
double p;
for(int i=0;i<n;i++){
scanf("%d %lf",&v,&p);
p=1-p;
for(int j=m;j>=v;j--){
f[j]= min(f[j], f[j-v]*p);
}
}
printf("%.1lf%%\n",(1-f[m])*100);
}
return 0;
}
三.存在性问题
1.Big events in HDU
用f[i][j]表示前i个物品中，是否能凑出价值j
则f[i][j]=f[i-1][j]|f[i-1][j-v]，其中v是第i个物品的价值
#include <bits/stdc++.h>
using namespace std;
const int N = 250010;
bool f[N];
int main(){
int T;
while(scanf("%d",&T)){
if(T<0) break;
memset(f,0,sizeof f);
f[0]=1;
int m=0;
while(T--){
int v,num;
scanf("%d %d",&v,&num);
while(num--){
m+=v;
for(int j=m;j>=v;j--) f[j]|=f[j-v];
}
}
for(int i=(m>>1);i>=0;i--){
if(f[i]){
printf("%d %d\n",m-i,i);
break;
}
}
}
return 0;
}
2.三角牧场Triangular Pastures
设sum为三角形周长，p为半周长
法一：dfs，用f[i][a][b]表示只考虑了前i条边，第一条边长为a，第二条边长为b的情况是否走过，这里保证a<=b
加上几个剪枝即可：
1.当a超过总周长的1/3时直接返回；
2.当a>b时直接返回
3.当f[i][a][b]已经走过则直接返回
注意1：f[i][a][b]表示的是当前两边长度分别为a和b，但第三边是前i条边总长-a-b，而不是sum-a-b!!!!
注意2：这里a和b是等价的，a>b可以直接剪枝。但c和a、b并不等价，因此b>c时不能直接剪枝
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 45 , M = 1605;
int w[N];
int n;
double ans;
int sum;
double p;
bool f[N][M][M];//第1条边为a，第2条边为b的情况是否出现过
//当前走到第i条边，两边分别为a b ，保证a<=b
void dfs(int i,int a,int b){
if(a>b || a>sum/3) return ;
if(f[i][a][b]) return ;
f[i][a][b]=1;
if(i==n){
int c=sum-a-b;
double tmp = sqrt(p*(p-a)*(p-b)*(p-c));
if(tmp>ans) ans=tmp;
return ;
}
dfs(i+1,a+w[i],b);
dfs(i+1,a,b+w[i]);
dfs(i+1,a,b);
}
int main(){
cin >> n;
for(int i=0;i<n;i++){
cin >> w[i];
sum+=w[i];
}
p=1.0*sum/2;
dfs(0,0,0);
if(ans==0) puts("-1");
else printf("%d\n",(int)(ans*100));
return 0;
}
法二：二维01背包存在性
f[i][j][k]表示前i个物品中，两边长分别为j、k的方案是否存在
则f[i][j][k] = (k>=w[i] && f[i-1][j][k-w[i]]) || (j>=w[i] && f[i-1][j-w[i]][k])
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 45 , M = 1605;
int w[N];
int n;
double ans;
int sum;
bool f[M][M];//第1条边为a，第2条边为b的情况是否出现过
int main(){
cin >> n;
for(int i=0;i<n;i++){
cin >> w[i];
sum+=w[i];
}
double pd=1.0*sum/2;
int pi = (int)pd;
f[0][0]=1;
for(int i=0;i<n;i++){
for(int j=pi;j>=0;j--){
for(int k=pi;k>=0;k--){
if(j>=w[i])
f[j][k]|=f[j-w[i]][k];
if(k>=w[i])
f[j][k]|=f[j][k-w[i]];
}
}
}
for(int i=0;i<=pi;i++){
for(int j=0;j<=pi;j++){
int k=sum-i-j;
if(f[i][j] && i+j>k && i+k>j && j+k>i){
double area = sqrt(pd*(pd-i)*(pd-j)*(pd-k));
ans = max(ans,area);
}
}
}
if(ans==0) puts("-1");
else printf("%d\n",(int)(ans*100));
return 0;
}
