首先我是按这篇文章来确定题目的。
poj3624 Charm Bracelet
模板题
没有要求填满，所以初始化为0就行
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int w[3403];
int h[3403];
int n,m;
int dp[12880+9];
int main()
{
// freopen("input.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d%d",&w[i],&h[i]);
for(int i=0;i<n;i++)
for(int j=m;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+h[i]);
printf("%d\n",dp[m]);
}
poj3628 Bookshelf 2
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int h[25];
int dp[21000000];
int n,s;
int sum;
int main()
{
// freopen("input.txt","r",stdin);
scanf("%d%d",&n,&s);
for(int i=0;i<n;i++){
scanf("%d",&h[i]);
sum+=h[i];
}
int ans=0;
for(int i=0;i<n;i++)
for(int j=sum;j>=h[i];j--)
dp[j]=max(dp[j],dp[j-h[i]]+h[i]);
for(int i=0;i<=sum;i++)
if(dp[i]>=s){
ans=dp[i]-s;
break;
}
printf("%d\n",ans);
}
poj3211 Washing Clothes
这道题就是两个人同时在一个盆子里洗衣服，算的时候每件衣服独立算，然后相同衣服之间可以连续，我们需要求得是在一半体积下那个花的时间大的值。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<iostream>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
int n,m;
map<string,int> q;
int w[105];
vector<int> g[11];
int dp[50000];
int main()
{
// freopen("input.txt","r",stdin);
while(scanf("%d%d",&n,&m)==2&&n&&m)
{
string str;
memset(w,0,sizeof(w));
q.clear();
for(int i=0;i<=10;i++)
g[i].clear();
for(int i=0;i<n;i++)
{
cin>>str;
q[str]=i;
}
for(int i=0;i<m;i++)
{
int t,v;
cin>>v>>str;
t=q[str];
g[t].push_back(v);
w[t]+=v;
}
int ans=0;
for(int i=0;i<n;i++)
{
int v=w[i]/2;
memset(dp,0,sizeof(dp));
for(int j=0;j<g[i].size();j++)
for(int k=v;k>=g[i][j];k--)
{
dp[k]=max(dp[k],dp[k-g[i][j]]+g[i][j]);
}
ans+=(w[i]-dp[v]);
}
printf("%d\n",ans);
}
}
poj1745 Divisibility
这道题如果取摸后范围比较小，第二维不大于100，然后记忆化背包（非递归搜索），根据能达到的值推能达到的值，衍生出前n个时的所有状态。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<iostream>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
int n,k;
int c[10005];
int dp[10005][105];
int main()
{
//freopen("input.txt","r",stdin);
int t;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&t);
if(t<0) t=-t;
t%=k;
c[i]=t;
}
dp[0][c[0]]=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<k;j++)
{
if(dp[i-1][j])
{
dp[i][(j+c[i])%k]=1;
dp[i][(j+k-c[i])%k]=1;
}
}
}
if(dp[n-1][0])
printf("Divisible\n");
else
printf("Not divisible\n");
}
poj1976 A Mini Locomotive
3辆车运货，共有n堆货，每辆可以运连续k堆，求最大运货量
保证k*3<=n;也就是说要运货量最大必须堆数为k。
dp[i][j]为前j次前i堆最大运货量的最大运货量
如果i<j*k;那么只能全运
第i堆不运：dp[i-1][j]
第i堆运：dp[i-k][j-1]+sum;
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int a[50005];
int n,k;
int dp[50005][4];
int main()
{
//freopen("input.txt","r",stdin);
int cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
a[0]=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]+=a[i-1];
}
scanf("%d",&k);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=3;j++)
{
if(i<j*k)
dp[i][j]=i;
else
dp[i][j]=max(dp[i-1][j],dp[i-k][j-1]+a[i]-a[i-k]);
}
}
printf("%d\n",dp[n][3]);
}
}
poj1837 Balance
状态压缩求方案数
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int k,n,f;
int dp[21][15100];
int h[21];
int w[21];
int main()
{
// freopen("input.txt","r",stdin);
scanf("%d%d",&f,&n);
for(int i=0;i<f;i++)
scanf("%d",&h[i]);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
dp[0][7500]=1;
for(int i=1;i<=n;i++)
{
for(int k=0;k<=15000;k++)
{
if(dp[i-1][k])
{
for(int j=0;j<f;j++)
{
dp[i][k+h[j]*w[i]]+=dp[i-1][k];
}
}
}
}
printf("%d\n",dp[n][7500]);
}
poj1948 Triangular Pastures
n个线，组一个三角形，求三角形的最大面积。
海伦公式
-
，p为半周长
因为周长已知，知道两条边就能确定面积。
设dp[i][j]（i>j),然后确定每一条边是否加入那个边，由已知状态推出未知状态，随之更新最大面积。
每条边不可能超过周长的一半。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int n;
int a[45];
int c;
int dp[1605][1605];
int aa[4];
// a+b>c-a-b
//
int check(int x,int y)
{
aa[0]=x;
aa[1]=y;
aa[2]=c-x-y;
if(aa[0]+aa[1]<aa[2]||aa[1]+aa[2]<aa[0]||aa[0]+aa[2]<aa[1])
return -1.0;
double t=c*1.0/2;
double ans=sqrt(t*(t-aa[0])*(t-aa[1])*(t-aa[2]))*100.0;
return ans;
// printf("%d %d %d %d\n",aa[0],aa[1],aa[2],(int)ans);
} int main()
{
// freopen("input.txt","r",stdin);
//printf("")
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
c+=a[i];
}
dp[0][0]=1;
int ans=-1.0;
for(int i=0;i<n;i++)
{
for(int j=c/2;j>=0;j--)
{
for(int k=c/2;k>=j;k--)
{
if(j>=a[i]&&dp[j-a[i]][k])
dp[j][k]=1;
if(k>=a[i]&&dp[j][k-a[i]])
dp[j][k]=1;
if(dp[j][k])
ans=max(ans,check(j,k));
// printf("%d\n",ans);
}
}
}
printf("%d\n",ans);
}
poj2923
待定