先来看一下经典的背包问题吧
http://www.cnblogs.com/Kalix/p/7617856.html 01背包问题
https://www.cnblogs.com/Kalix/p/7622102.html 完全背包问题
https://blog.csdn.net/mystery_guest/article/details/51878140 多重背包二进制优化
1.https://cn.vjudge.net/problem/12304/origin POJ 3176
从上往下走或者右下走找最大总和，也可以不同dp写。
注意动态规划这一步一定是和上一步或下一步有关联的
//dp[i][j]表示走到i，j这步时的最大值
for(i=;i<=n;i++)
{
for(j=;j<=i;j++)
{
dp[i][j]=max(dp[i-][j],dp[i-][j-])+map[i][j];//（i，j）这一步是从（i-1，j）或者（i-1，j-1）走过来的
ans=max(ans,dp[i][j]);
} }
全部代码
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
int n,map[][],dp[][];
int ans=; int main()
{
cin>>n;
for(int i=;i<=n;i++)
{
for(int j=;j<=i;j++)
{
cin>>map[i][j];
}
}
int i,j;
for(i=;i<=n;i++)
{
for(j=;j<=i;j++)
{
dp[i][j]=max(dp[i-][j],dp[i-][j-])+map[i][j];
ans=max(ans,dp[i][j]);
} }
cout<<ans;
}
2.https://cn.vjudge.net/problem/30465/origin POJ 2229
这题是看一个数能用几个不同二次方幂的数和表示
首先来练习一下深搜把，这一开始我没想到还能用深搜，尽管不对，当然可慢啦啦啦啦
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int ans;
long long p[];
void dfs(int n,int last)
{
if(n==)
{
ans++;
return;
}
for(int i=;n-p[i]>=;i++)
{
if(p[i]>=last)
dfs(n-p[i],p[i]);
}
}
int main()
{
int n;
for(int i=;i<=;i++)
p[i]=pow(,i);
cin>>n;
dfs(n,);
printf("%d",ans); return ;
}
接下来是dp版的，不知道为啥，还是超时！！！！，但思想要学习下，看懂下面的那个dp更新表就欧克了
dp表假设只有1，然后添加2，然后添加4然后添加8，更新表
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
long long dp[],p[];
int main()
{
int n; while(scanf("%d",&n)!=EOF)
{
memset(dp,,sizeof(dp));
p[]=dp[]=;
for(int i=;i<=;i++)
{
p[i]=p[i-]<<;
}
for(int i=;i<=;i++)
{
if(p[i]<=n)
{
for(int j=p[i];j<=n;j++)
{
dp[j]=(dp[j]+dp[j-p[i]])%;
}
}
}
/*dp 1 2 3 4 5 6 7//假设输入7
1 1 1 1 1 1 1 1
2 2 2 3 3 4 4
4 4 4 6 6
*/
cout<<dp[n]<<endl;
} }
最后过的是这个，我他喵。。。
#include<iostream>
#include<string.h>
using namespace std;
long long a[];
int main()
{
int n;
a[]=,a[]=;
for(int i=;i<;i++)
{
a[i]=a[i-]+a[i/];
a[i]%=;
}
cin>>n;
cout<<a[n];
}
1.n为奇数，a[n]=a[n-1]
2.n为偶数：
（1）如果加数里含1，则一定至少有两个1，即对n-2的每一个加数式后面 +1+1，总类数为a[n-2]；
（2）如果加数里没有1，即对n/2的每一个加数式乘以2，总类数为a[n/2]；
3.https://cn.vjudge.net/problem/18264/origin POJ 2385
题意有两棵树1，2，掉苹果，人一开始在1下，有指定的移动次数，给苹果下落，求最多接到的苹果数
首先想一想，跟平常的题有什么区别
1.人会移动，
2.苹果要判断是否要不移动接到，还是移动接到
3.移动的次数不像是背包问题里的背包容量越多越好，但和背包问题类似
for(int i=;i<=n;i++)
{
dp[i][]=dp[i-][];//第i个苹果，j次移动的最好结果，判断一直不动的情况
if(t[i]==) dp[i][]++; for(int j=;j<=w;j++)
{
if(j%+==t[i]){//判断移动后的位置在哪，如果跟这次下落苹果的位置一样
dp[i][j]=max(dp[i-][j],dp[i-][j-])+;//dp的关键，跟上次的东西有关联，接这个苹果我可以选择i-1个苹果移动相同的次数，然后不动接
//也可以从另一个苹果树移动过来接
}
else
dp[i][j]=max(dp[i-][j],dp[i-][j-]);
}
}
整体代码
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int t[];
int dp[][];
int main()
{
int n,w;
cin>>n>>w;
for(int i=;i<=n;i++)
{
cin>>t[i];
} memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
{
dp[i][]=dp[i-][];
if(t[i]==) dp[i][]++; for(int j=;j<=w;j++)
{
if(j%+==t[i]){
dp[i][j]=max(dp[i-][j],dp[i-][j-])+;
}
else
dp[i][j]=max(dp[i-][j],dp[i-][j-]);
}
}
cout<<dp[n][w]<<endl;
}
4.https://cn.vjudge.net/problem/16276/origin POJ 3616
给定时间段，每个时间段有工作效率，每个时间段都要休息，求最大工作量
1.首先想到的是要对这些时间段排序，根据结束时间
2.对他们进行动态规划，具体思想可以参考求一个序列的最大上升子序列
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
struct node{
int s,e,ef; }x[];
bool cmp(node a,node b){
return a.e<b.e;
}
int dp[];
int main()
{
int a,b,c;
cin>>a>>b>>c;
for(int i=;i<=b;i++)
{
cin>>x[i].s>>x[i].e>>x[i].ef;
x[i].e+=c;
}
sort(x+,x++b,cmp);
memset(dp,,sizeof(dp));
int ans=;
for(int i=;i<=b;i++)
{
dp[i]=x[i].ef;
for(int j=;j<i;j++)
{
if(x[i].s>=x[j].e)
{
dp[i]=max(dp[i],dp[j]+x[i].ef);//判断选这个或者不选这个，根据工作量大小
}
}
ans=max(ans,dp[i]);
}
cout<<ans; }
牛客多校第二场a题
一个人可以走一步或者跳x步，但不能连着跳，问到这个区间里有几种走法
考虑两种状态 对于这一点，我可以走过来，前面是怎么样的我不用管，也可以跳过来但是，跳过来必须保证前一步是走的
dp[i][0]表示i这一步是走过来的dp[i][1]表示i这一步是跳过来的
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
long long dp[][];
long long mod=1e9+;
long long ans[];
int main()
{
int n,w;
cin>>n>>w;
dp[][]=;
for(int i=;i<=;i++)
{
dp[i][]=(dp[i-][]+dp[i-][])%mod;
if(i>=w) dp[i][]=dp[i-w][]%mod;
} for(int i=;i<=;i++)
{
ans[i]=(dp[i][]+dp[i][]+ans[i-])%mod;
}
//for(int i=1;i<=10;i++)
//cout<<ans[i]<<endl; while(n--)
{
long long l,r;
cin>>l>>r;
cout<<(ans[r]-ans[l-]+mod)%mod<<endl;
}
return ;
}
[POJ-3280]
给一串字符串，添加字母或者去掉字母使其变成回文串，不过有代价 ，让代价最小
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m,dp[][],t[],k,p;
int main()
{
char s[],a[];
while(cin>>n>>m)
{
memset(dp,,sizeof(dp));
cin>>a;
for(int i=;i<n;i++)
{
cin>>s>>k>>p;
t[s[]-'a']=min(k,p);
}
for(int i=;i<m;i++)
{
for(int j=i-;j>=;j--)
{
dp[j][i]=min(dp[j+][i]+t[a[j]-'a'],dp[j][i-]+t[a[i]-'a']);
if(a[i]==a[j])
dp[j][i]=min(dp[j+][i-],dp[j][i]);
}
}
cout<<dp[][m-]<<endl; }
}
：Tony想要买一个东西，他只有n中硬币每种硬币的面值为a[i]每种硬币的数量为c[i]要买的物品价值不超过m
多重背包的二进制优化
#include <iostream>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
int f[],a[],c[];
int n,m; //m背包的总容量、v物品的体积、w物品的价值
void OneZeroPack(int m,int v,int w) //0-1背包
{
for(int i=m;i>=v;i--)
f[i]=max(f[i],f[i-v]+w);
} //m背包的总容量、v物品的体积、w物品的价值
void CompletePack(int m,int v,int w) //完全背包
{
for(int i=v;i<=m;i++)
f[i]=max(f[i],f[i-v]+w);
} //m背包的总容量、v物品的体积、w物品的价值、num物品的数量
void MultiplePack(int m,int v,int w,int num)//多重背包
{
if(v*num>=m)
{
CompletePack(m,v,w);
return ;
}
int k=;
for(k=;k<=num;k<<=)
{
OneZeroPack(m,k*v,k*w);
num=num-k;
}
if(num)
OneZeroPack(m,num*v,num*w);
} int main()
{
while(cin>>n>>m)
{
if(n==&&m==) break;
for(int i=;i<n;i++)
cin>>a[i];
for(int i=;i<n;i++)
cin>>c[i];
for(int i=;i<=m;i++) f[i]=-INF;
f[]=;
for(int i=;i<n;i++)
{
MultiplePack(m,a[i],a[i],c[i]);
}
int sum=;
for(int i=;i<=m;i++)
if(f[i]>) sum++;
cout<<sum<<endl;
}
return ;
}
hdu 2089
http://acm.hdu.edu.cn/showproblem.php?pid=2089
算是数位dp的入门吧
求n到m之间数字中没有4和62（连着）的个数
#include <algorithm>
#include <iostream>
using namespace std; int dp[][]; void init(){
dp[][] = ;//dp[0][1-9] = 1都可以
for(int i = ; i <= ; i++)
for(int j = ; j < ; j++)//i位
for(int k = ; k < ; k++)//i-1位
if(j != && !(j == && k == ))
dp[i][j] += dp[i-][k];
} int solve(int n){
int d[];
int len = ; while(n > ){//数组保存
d[++len] = n%;
n /= ;
} d[len + ] = ; int ans = ; for(int i = len; i >= ; i--){ for(int j = ; j < d[i]; j++){
if(j != && !(d[i+] == && j == )) ans += dp[i][j];//求和
} if(d[i] == || (d[i] == && d[i+] == )) break;//判出 } return ans;
} int main()
{ int r, l;
init();
while(cin>>l>>r){
if(r + l == ) break; cout<<solve(r+) - solve(l)<<endl;
}
return ;
}
题目大意：蚂蚁牙黑，蚂蚁牙红：有A只蚂蚁，来自T个家族，分别记为ant[i]个。同一个家族的蚂蚁长得一样，但是不同家族的蚂蚁牙齿颜色不同。任取n只蚂蚁(S <= n <= B)，求能组成几种集合？
状态：dp[i][j]：前i种中选j个可以组成的种数
决策：第i种选k个，k<=ant[i] && j-k>=0
转移：dp[i][j]=Σdp[i-1][j-k]
#include<stdio.h>
#include<string.h>
int dp[][];
int num[];
int main(){
int n,m,a,b,x;
while(scanf("%d%d%d%d",&n,&m,&a,&b)!=EOF){
memset(num,,sizeof(num));
for(int i=;i<m;i++){
scanf("%d",&x);
num[x]++;
}
memset(dp,,sizeof(dp));
for(int i=;i<=num[];i++) dp[][i]=;
for(int i=;i<=n;i++){
for(int j=;j<=b;j++){
for(int k=;k<=num[i];k++){
if(j>=k) {
dp[i][j]+=dp[i-][j-k];
dp[i][j]%=;
}
}
}
}
int ans=;
for(int i=a;i<=b;i++){
ans+=dp[n][i];
ans%=;
}
printf("%d\n",ans);
}
return ;
}
还有一种
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-ant[i]-1]
#include<iostream>
using namespace std;
#define MOD 1000000
int T, A, S, B;
int ant[];
int dp[][];
int ans;
int main()
{
scanf("%d%d%d%d", &T, &A, &S, &B);
for (int i = ; i <= A; i++)
{
int aa;
scanf("%d", &aa);
ant[aa]++;
}
dp[][] = dp[][] = ;
for (int i = ; i <= T; i++)
for (int j = ; j <= B; j++)
if (j - ant[i] - >= ) dp[i % ][j] = (dp[(i - ) % ][j] + dp[i % ][j - ] - dp[(i - ) % ][j - ant[i] - ] + MOD) % MOD; //在取模时若出现了减法运算则需要先+Mod再对Mod取模，防止出现负数（如5%4-3%4为负数）
else dp[i % ][j] = (dp[(i - ) % ][j] + dp[i % ][j - ]) % MOD;
for (int i = S; i <= B; i++)
ans = (ans + dp[T % ][i]) % MOD;
printf("%d\n", ans);
return ;
}