poj3624 Charm Bracelet
模板题
没有要求填满，所以初始化为0就行
#include<cstdio>
#include<iostream>
using namespace std;
#define N 15010
int n,m,v[N],c[N],f[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
for(int i=;i<=n;i++){
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+c[i]);
}
}
printf("%d\n",f[m]);
return ;
}
poj3628 Bookshelf 2
#include<cstdio>
#include<iostream>
using namespace std;
#define N 21000000
int n,m,sum,ans,c[],f[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&c[i]),sum+=c[i];
for(int i=;i<=n;i++){
for(int j=sum;j>=c[i];j--){
f[j]=max(f[j],f[j-c[i]]+c[i]);
}
}
for(int i=;i<=sum;i++){
if(f[i]>=m){
ans=f[i]-m;break;
}
}
printf("%d\n",ans);
return ;
}
poj1745 Divisibility
这道题如果取摸后范围比较小，第二维不大于100，然后记忆化背包（非递归搜索），根据能达到的值推能达到的值，衍生出前n个时的所有状态。
#include<cstdio>
#include<iostream>
using namespace std;
#define N 10005
int n,k,c[N];
bool f[N][];
int main(){
scanf("%d%d",&n,&k);
for(int i=,x;i<n;i++){
scanf("%d",&x);
if(x<) x=-x;
c[i]=x%k;
}
f[][c[]]=;
for(int i=;i<n;i++){
for(int j=;j<k;j++){
if(f[i-][j]){
f[i][(j+c[i])%k]=;
f[i][(j+k-c[i])%k]=;
}
}
}
puts(f[n-][]?"Divisible":"Not divisible");
return ;
}
poj1976 A Mini Locomotive
3辆车运货，共有n堆货，每辆可以运连续k堆，求最大运货量
保证k*3<=n;也就是说要运货量最大必须堆数为k。
f[i][j]为前j次前i堆最大运货量的最大运货量
如果i<j*k;那么只能全运
第i堆不运：f[i-1][j]
第i堆运：f[i-k][j-1]+sum;
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define N 50010
int n,k,T,s[N],f[N][];
int main(){
scanf("%d",&T);
while(T--){
memset(f,,sizeof f);
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&s[i]),s[i]+=s[i-];
scanf("%d",&k);
for(int i=;i<=n;i++){
for(int j=;j<=;j++){
if(i<j*k)
f[i][j]=i;
else
f[i][j]=max(f[i-][j],f[i-k][j-]+s[i]-s[i-k]);
}
}
printf("%d\n",f[n][]);
}
return ;
}
poj1837 Balance
状态压缩求方案数
注意要平移数组
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define p 7500
#define N 21
int n,m,h[N],w[N],f[N][p*+];
int main(){
scanf("%d%d",&m,&n);
for(int i=;i<m;i++) scanf("%d",&h[i]);
for(int i=;i<=n;i++) scanf("%d",&w[i]);
f[][p]=;
for(int i=;i<=n;i++){
for(int k=;k<=p<<;k++){
if(f[i-][k]){
for(int j=;j<m;j++){
f[i][k+h[j]*w[i]]+=f[i-][k];
}
}
}
}
printf("%d\n",f[n][p]);
return ;
}
poj1948 Triangular Pastures
n个线，组一个三角形，求三角形的最大面积。
海伦公式
-
，p为半周长
因为周长已知，知道两条边就能确定面积。
设f[i][j]（i>j),然后确定每一条边是否加入那个边，由已知状态推出未知状态，随之更新最大面积。
每条边不可能超过周长的一半。
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
#define M 45
#define N 1605
int n,c,a[M];
bool f[N][N];
int ans=-0x7fffffff;
int check(int x,int y){
double t1=x;
double t2=y;
double t3=c-x-y;
if(t1+t2<t3||t1+t3<t2||t3+t2<t1) return -1.0;
double t=c*1.0/2.0;
double res=sqrt(t*(t-t1)*(t-t2)*(t-t3))*100.0;
return res;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",a+i),c+=a[i];
f[][]=;
for(int i=;i<=n;i++){
for(int j=c>>;j>=;j--){
for(int k=c>>;k>=j;k--){
if(j>=a[i]&&f[j-a[i]][k]) f[j][k]=;
if(k>=a[i]&&f[j][k-a[i]]) f[j][k]=;
if(f[j][k]) ans=max(ans,check(j,k));
}
}
}
printf("%d\n",ans);
return ;
}