本文文旨，如题...
转载请注明出处...
HDOJ 1176 免费馅饼
http://acm.hdu.edu.cn/showproblem.php?pid=1176
类似数塔，从底往上推，每次都是从下面三个中选最大的
#include<cstdio>
#include<cstring>
#define MAXN 100005
int dp[MAXN][];//第i秒第j个位置的馅饼数
int max1(int a,int b)
{
return a>b?a:b;
}
int max2(int a,int b,int c)
{
return a>b?(a>c?a:c):(b>c?b:c);
}
int main()
{
int n,x,t,T;
while(~scanf("%d",&n))
{
if(n==) break;
T=;
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
{
scanf("%d%d",&x,&t);
dp[t][x]++;
if(T<t) T=t;//时间不一定递增的，找到最大的时间
}
for(int i=T;i>=;i--)//从底往上一层一层的加
{
for(int j=;j<=;j++)
{
if(j==) dp[i][j]+=max1(dp[i+][],dp[i+][]);
else if(j==) dp[i][j]+=max1(dp[i+][],dp[i+][]);
else dp[i][j]+=max2(dp[i+][j+],dp[i+][j],dp[i+][j-]);
}
}
printf("%d\n", dp[][]);//起始位置在5
}
return ;
}
HDOJ 4540 威威猫系列故事--打地鼠
http://acm.hdu.edu.cn/showproblem.php?pid=4540
也是数塔，从上往下，从下往上都可以，只不过每次是在下面一层中选最优的
#include<cstdio>
#include<cstring>
int n,k,a[][],dp[][];
int abss(int a)
{
return a>?a:-a;
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=k;j++)
{
scanf("%d",&a[i][j]);//第i秒第j个位置有老鼠
}
}
memset(dp,,sizeof(dp));
int tmp,cur,ans=;
for(int i=n-;i>=;i--)//从下往上选最优
{
for(int j=;j<=k;j++)
{
tmp=;
for(int m=;m<=k;m++)
{
cur=abss(a[i][j]-a[i+][m])+dp[i+][m];
if(cur<tmp)
{
tmp=cur;
}
}
dp[i][j]+=tmp;
}
}
for(int i=;i<=k;i++)//最后在第一层中选出最小的
{
if(dp[][i]<ans)
{
ans=dp[][i];
}
}
printf("%d\n", ans);
}
return ;
}
HDOJ 1087 Super Jumping！
http://acm.hdu.edu.cn/showproblem.php?pid=1087
各项和最大的LIS
#include<cstdio>
#define MAXN 1010
#define LL long long
LL a[MAXN],dp[MAXN],ans;
int n;
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==) break;
for(int i=;i<n;i++)
{
scanf("%lld",&a[i]);
}
for(int i=;i<n;i++)
{
dp[i]=a[i];//dp[i]保存的是到i为止满足题意的和的最大值
}
for(int i=;i<n;i++)
{
ans=;
for(int j=;j<i;j++)//在i前面找到一个满足题意的且和最大的
{
if(a[i]>a[j]&&dp[j]>ans)
{
ans=dp[j];
}
}
dp[i]+=ans;
}
ans=;
for(int i=;i<n;i++)
{
if(dp[i]>ans)
ans=dp[i];
}
printf("%lld\n", ans);
}
return ;
}
HDOJ 1160 FatMouse's speed
http://acm.hdu.edu.cn/showproblem.php?pid=1160
类似LIS，要输出序列，这份代码写的比较搓...
#include<cstdio>
#include<algorithm>
#define MAXN 1010
using namespace std;
struct mouse
{
int w,s,no,l,pre;//重量、速度、编号、以此老鼠为结尾的满足题意序列的最长长度、在满足题意序列中的前驱(用于输出路径)
};
mouse mice[MAXN],tmp;
bool cmp(mouse a,mouse b)
{
if(a.w==b.w) return a.s>b.s;
return a.w<b.w;
}
bool cmp2(mouse a,mouse b)
{
return a.no<b.no;
}
int main()
{
int tot=,cur,k;
while(scanf("%d%d",&tmp.w,&tmp.s)!=EOF)
{
tmp.no=++tot;
tmp.l=;
tmp.pre=tot;
mice[tot]=tmp;
}
sort(mice+,mice+tot+,cmp);
for(int i=;i<=tot;i++)
{
cur=; k=mice[i].no;
for(int j=;j<i;j++)
{
if(mice[j].w<mice[i].w&&mice[j].s>mice[i].s&&mice[j].l>cur)
{
cur=mice[j].l;
k=mice[j].no;
}
}
mice[i].l+=cur;
mice[i].pre=k;
}
cur=;k=;
for(int i=;i<=tot;i++)
{
if(mice[i].l>cur)
{
cur=mice[i].l;
k=mice[i].no;
}
}
sort(mice+,mice+tot+,cmp2);
printf("%d\n", cur);
tmp=mice[k];
int top=-,print[MAXN];
for(int i=;i<=cur;i++)//最后拿个栈输出的
{
print[++top]=tmp.no;
tmp=mice[tmp.pre];
}
while(top>-)
{
printf("%d\n",print[top--]);
} }
HDOJ 1159 Common Subsequence
http://acm.hdu.edu.cn/showproblem.php?pid=1159
LCS 经典DP
#include<cstdio>
#include<cstring>
#define MAXN 1005
char str1[MAXN],str2[MAXN];
int dp[MAXN][MAXN];
int mmax(int a,int b)
{
return a>b?a:b;
}
int main()
{
while(~scanf("%s",str1))
{
scanf("%s",str2);
memset(dp,,sizeof(dp));
int n=strlen(str1);
int m=strlen(str2);
for(int i=;i<=n;i++)//按着状态转移方程写就行了，也没什么细节...
{
for(int j=;j<=m;j++)
{
if(str1[i-]==str2[j-])
{
dp[i][j]=dp[i-][j-]+;
}else
{
dp[i][j]=mmax(dp[i-][j],dp[i][j-]);
}
}
}
printf("%d\n", dp[n][m]);
}
return ;
}
HDOJ 1423 Greatest Common Increasing Subsequence
http://acm.hdu.edu.cn/showproblem.php?pid=1423
LCIS 网上方法也很多了 这里贴个O(n^2)的...具体详细解释请看代码注释中的模拟过程...
#include<cstdio>
#include<cstring>
#define MAXN 510
#define REP(i,a,b) for(int i=a;i<b;i++)
int a[MAXN],b[MAXN],dp[MAXN],n,m,T,max;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
REP(i,,n) scanf("%d",&a[i]);
scanf("%d",&m);
REP(i,,m) scanf("%d",&b[i]);
memset(dp,,sizeof(dp));
/*看不懂的建议自己先动手模拟一遍
表面上dp[]是一维的，其实它代表的是dp[i,j]
1 4 2 6 3 8 5 9 1
2 7 6 3 5 1
比如上面这两个序列：
i=0:把dp[5]置为1,因为有相等的
i=1:虽然在b[5]时，max=1了，但是b后面并没有4了，所以也没有更新
i=2:把dp[0]置为1
i=3:这一步比较关键了，理解了就懂这个算法了 a[3]=6
j=0时，把max更新为1，这代表在6之前a里面已经有一个2与b里面的匹配了
所以此时的max=1，如果在b里面2的后面还能找到一个6，那么就把dp[2]置为2
因为起码有个2 6是公共上升子序列了
i=4......后面的一步步模拟 到i=6即a[6]=5的时候是最大的3 把dp[4]置为3
...最后遍历一遍dp数组找到最大的值即为所求
*/
REP(i,,n) {
max=;
REP(j,,m) {
if(a[i]>b[j]&&dp[j]>max) max=dp[j];
if(a[i]==b[j]) dp[j]=max+;
}
}
max=;
REP(i,,m) if(dp[i]>max) max=dp[i];
printf("%d\n",max);
if(T) printf("\n");
}
return ;
}
COJ 1120 病毒
http://122.207.68.93/OnlineJudge/problem.php?id=1120
第八届湖南省赛的题目 裸的LCIS...
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=;
int a[maxn],b[maxn],dp[maxn];
int n,m;
int LICS()
{
int MAX,i,j;
memset(dp,,sizeof(dp));
for(i=;i<n;i++)
{
MAX=;
for(j=;j<m;j++)
{
if(a[i]>b[j] && MAX<dp[j])
MAX=dp[j];
if(a[i]==b[j])
dp[j]=MAX+;
}
}
MAX=;
for(i=;i<m;i++)
if(dp[i]>MAX)
MAX=dp[i];
return MAX;
}
int main()
{
int t,i;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(i=;i<m;i++)
scanf("%d",&b[i]);
printf("%d\n",LICS());
}
return ;
}#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=;
int a[maxn],b[maxn],dp[maxn];
int n,m;
int LICS()
{
int MAX,i,j;
memset(dp,,sizeof(dp));
for(i=;i<n;i++)
{
MAX=;
for(j=;j<m;j++)
{
if(a[i]>b[j] && MAX<dp[j])
MAX=dp[j];
if(a[i]==b[j])
dp[j]=MAX+;
}
}
MAX=;
for(i=;i<m;i++)
if(dp[i]>MAX)
MAX=dp[i];
return MAX;
}
int main()
{
int t,i;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(i=;i<m;i++)
scanf("%d",&b[i]);
printf("%d\n",LICS());
}
return ;
}
HDOJ 1257 最少拦截系统
http://acm.hdu.edu.cn/showproblem.php?pid=1257
平常的导弹题是求最多拦多少导弹，就是求出一个最长的不增子序列...
这题问至少要安装多少套系统，其实就是找出最长的严格递增子序列的长度，即LIS
好像有个定理是证这个的，不过手写一个序列模拟一下也能看出来...
给出两个版本吧...一个O(n^2)的 一个O(nlogn)的...具体看代码注释
#include<cstdio>
#include<cstring>
#define MAXN 1005
int a[MAXN],dp[MAXN],n,max;//这个dp[i]存的是以i为结尾的最长递增子序列的长度
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<n;i++) scanf("%d",&a[i]);
memset(dp,,sizeof(dp));
for(int i=;i<n;i++)
{
max=;
for(int j=;j<i;j++)//转移方程dp[i]=max{dp[j]+1} 其中j要满足的a[i]>a[j]
{
if(a[i]>a[j]&&dp[j]>max) max=dp[j];//因为要找到这个最大值 所以从0到i遍历了一遍
}
dp[i]=max+;
}
for(int i=;i<n;i++) max=max>dp[i]?max:dp[i];
printf("%d\n",max);
}
return ;
}
#include<cstdio>
#include<cstring>
#define MAXN 1005
int a[MAXN],dp[MAXN],n;
/*
这个版本的dp[i]存的就是a中长度为i的递增子序列末尾数的最小值
比较绕口 给个序列吧：2 1 4 3 5 数组下标从1开始
a[1]=2 dp[1]=2
a[2]=1 dp[1]=1
a[3]=4 dp[2]=4
a[4]=3 dp[2]=3
a[5]=5 dp[3]=5
最终dp更新到第几项 最长长度就是几 而不是dp里面存的数
更详细的模拟过程可以看这个
http://www.cnblogs.com/mengxm-lincf/archive/2011/07/12/2104745.html
二分部分的代码借鉴了这个
http://www.wutianqi.com/?p=1850
*/
int BSearch(int x,int k)
{
int low=,high=k,mid;
while(low<=high)
{
mid=(low+high)>>;
if(x>=dp[mid]) low=mid+;
else high=mid-;
}
return low;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<=n;i++) scanf("%d",&a[i]);
memset(dp,,sizeof(dp));
int k=; dp[k]=a[];
for(int i=;i<=n;i++)
{
if(a[i]>dp[k]) dp[++k]=a[i];
else dp[BSearch(a[i],k)]=a[i];
}
printf("%d\n",k);
}
return ;
}
HDOJ 1025 Constructing Roads In JGShining's Kingdom
http://acm.hdu.edu.cn/showproblem.php?pid=1025
这题也是一个裸的LIS 不过因为n比较大(<=500000) 用n^2的算法妥妥超时(如果出题人没有偷懒的话...)
按照上面写的nlogn的算法写就OK了...
#include<cstdio>
#include<cstring>
#define MAXN 500010
#define REP(i,a,b) for(int i=a;i<b;i++)
#define MEM(a) memset(a,0,sizeof(a))
int a[MAXN],dp[MAXN],n;
int BSearch(int x,int k)
{
int low=,high=k,mid;
while(low<=high)
{
mid=(low+high)>>;
if(x>=dp[mid]) low=mid+;
else high=mid-;
}
return low;
}
int main()
{
int cases=,x,y;
while(~scanf("%d",&n))
{
REP(i,,n+) {
scanf("%d%d",&x,&y);
a[x]=y;
}
MEM(dp);
int k=; dp[k]=a[];
REP(i,,n+) {
if(a[i]>dp[k]) dp[++k]=a[i];
else dp[BSearch(a[i],k)]=a[i];
}
printf("Case %d:\n",++cases);
printf("My king, at most %d road", k);//坑爹啊 road roads傻傻分不清楚
if(k!=) printf("s");
printf(" can be built.\n\n");
}
return ;
}
HDOJ 2602 Bone Collector
http://acm.hdu.edu.cn/showproblem.php?pid=2602
01背包 经典动规 给出两种方法吧 一种空间二维的 一种空间一维的
#include<cstdio>
#include<cstring>
#define MAXN 1005
int n,v,c[MAXN],w[MAXN],f[MAXN][MAXN];
int mmax(int a,int b)
{
return a>b?a:b;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&v);
for(int i=;i<=n;i++)
{
scanf("%d",&w[i]);
}
for(int i=;i<=n;i++)
{
scanf("%d",&c[i]);
}
memset(f,,sizeof(f));
for(int i=;i<=n;i++)//经典动规 f[i][j]表示把i件物品放入容量为j的背包中能获得的最大价值
{
for(int j=;j<=v;j++)//这里j要从0开始，从1开始就WA，这一点我到现在也没理解，各位大神谁看到了给我解释一下...
{
if(j>=c[i]) f[i][j]=mmax(f[i-][j],f[i-][j-c[i]]+w[i]);//按照转移方程写就OK了
else f[i][j]=f[i-][j];
}
}
printf("%d\n", f[n][v]);
}
return ;
}
这种一维的比较难理解一点，具体解释全在注释里了...
#include<cstdio>
#include<cstring>
#define MAXN 1005
int n,v,c[MAXN],w[MAXN],f[MAXN];
int mmax(int a,int b)
{
return a>b?a:b;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&v);
for(int i=;i<=n;i++)
{
scanf("%d",&w[i]);
}
for(int i=;i<=n;i++)
{
scanf("%d",&c[i]);
}
memset(f,,sizeof(f));
/*
状态转移方程是f[j]=max(f[j],f[j-c[i]]+w[i]) 代表背包容量为j的最大价值
这里f是一维的，但是其实后面max里面的f[j]表示的是f[i-1,j]，要做到这一点需要以j从v到0的逆序方式遍历
具体怎么理解呢，其实自己模拟一遍是最好的...
我们知道，实质上01背包问题的状态转移方程是f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i])
前面是不放第i件物品的策略，后面是放第i件物品的策略 但是要选择放策略的时候
需要的f[i-1][j-c[i]]这个值必须是没有放第i件物品计算出来的值，否则就不是01背包了，
因为每件物品你都可能放了多件
只有让j从v到0的遍历方式，才能保证在计算f[j]时用到的f[j-c[i]]是第i-1次的(即没有放第i件物品的)
比如c[i] 1 2 3 4 5//代价
w[i] 5 4 3 2 1//价值
如果j是从0到v的顺序遍历的，则算出来的dp[1]=5 在你算dp[2]的时候，此时调用的
dp[j]=max(dp[j],dp[j-c[i]]+w[i]) 你会得到dp[2]=dp[2-1]+w[1]=10
这个结果意味着容量为2的背包最大价值是10，而在01背包中这个值显然应该是4，原因就在于由于顺序遍历
造成了在计算dp[2]时，放了两件第1件物品 这在01背包中是不允许的
而采用逆序的方式则可以保证在计算dp[2]的时候，dp[1]还是0(在背包不要求装满的情况下，只要给dp初始化0就行)
这样就能保证每个物品至多放一次 自己按照逆序模拟一遍就能体会到这个策略的正确性了
ps：这里多说一句吧，其实按照j从0到v的方式遍历，刚好是另一种背包问题--完全背包的解法，这种背包问题中，
每个物品都有无限件可选，也就是上面的计算dp[2]得到10才是正确的
这种策略正确的原因就在于，完全背包问题实质上的转移方程是：
f[i][j]=max(f[i-1][j],f[i][j-c[i]]+w[i])--也分为两种策略 不放、放，但是放的话可以放无限件
细细体会吧...
更多背包问题的资料，请参考《背包九讲》...
*/
for(int i=;i<=n;i++)
{
for(int j=v;j>=c[i];j--)
{
f[j]=mmax(f[j],f[j-c[i]]+w[i]);
}
}
printf("%d\n", f[v]);
}
return ;
}
HDOJ 4512 吉哥系列故事——完美队形I
http://acm.hdu.edu.cn/showproblem.php?pid=4512
这题出的比较巧妙，可以另搞一个数组是原数组的逆序，然后求LCIS
对于中间点，是奇数时，简单判断一下是否用到了中间点，最后结果是2*k-1 否则就是2*k
具体见代码：
#include<cstdio>
#include<cstring>
using namespace std;
int n,ans,a[],dp[];
inline void Max(int &a,const int b){if(b>a) a=b;}
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(dp,,sizeof dp);
for(int i=;i<n;i++) scanf("%d",a+i);
ans=;
for(int k=n-;k>=;k--){
int x=a[k],mx=;
for(int i=;i<=k;i++){
if(a[i]<x) Max(mx,dp[i]);
else if(a[i]==x) dp[i]=mx+;
if(i<k) Max(ans,dp[i]*);
else Max(ans,dp[i]*-);
}
}
printf("%d\n",ans);
}
return ;
}
持续更新中...