很久没写DP了(大概一年之久),由此可鉴,没有付出足够的努力呀
在思考过程中一直警醒自己 不能看解题报告,于是乎,艰苦的独立完成了,虽然是俩简单的DP,但收获不小,吼吼~~~~~~
Super
Jumping! Jumping! Jumping!
这个题意是,一维空间上求和最大的一个可以不连续的序列,输出最大和。
推导DP的动态方程时,只需要找比当前值小的和的最大值加上当前的值,即为当前值的最大和,记录整个搜索过程中的最大和即为所求。
该题需要注意的是,Max值会超出int范围。
DP方程式为:
DP[i]=num[i]+max(DP[i-1,i-2....0]);
做题的时候一直WA,原因是,DP方程有误,max(DP[i-1,i-2....0]),误写成最接近当前num的DP。没有注意到最接近的不一定是和最大的。
如果求最大连续序列的和(有负值),输出开始点,结束点。只需要记录并修改begin值(和小于0时)和end值(和大于当前最大和时)即可。
FatMouse's
Speed
题意,weight严格递增,speed严格递减的Mice序列。
分析,可以借助sort对speed或者weight排序(记录Mice的编号)然后对另外一个属性,求单调递增子序列。并输出该序列及序列长度
找每个Mice的weight或speed比自己小的值的最大值,DP更新为 当前Mice应有的顺序号。记录整个DP过程中最大的排序号。
DP完毕倒序查找一个序列。
1160的代码:
#include<iostream>
using namespace std;
int num[1001];
long long dp[1001];
int main()
{
int n,i;
while (cin>>n&&n)
{
long long mx;
cin>>num[1];
dp[0]=0;
dp[1]=num[1];
mx=dp[1];
for(i=2;i<=n;i++)//DP过程
{
cin>>num[i];
long long mn=0;
for(int j=i-1;j>0;j--)
{
if(num[i]>num[j])
{
if(dp[j]>mn)
mn=dp[j];
}
}
dp[i]=num[i]+mn;
if(mx<dp[i]) mx=dp[i];
}
cout<<mx<<endl;
}
return 0;
}
1087的代码:
#include<iostream>
#include<algorithm>
using namespace std;
struct info
{
int w;
int s;
int f;
}Mice[1001];
bool compare(struct info a,struct info b)
{
if(a.s>b.s) return 1;
else if((a.s==b.s)&&(a.w<b.w)) return 1;
else return 0;
}
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int m,n;
int k=1;
while(cin>>m>>n)
{
Mice[k].w=m;
Mice[k].s=n;
Mice[k].f=k++;
}
sort(Mice,Mice+k,compare);
int i,j;
int len=0;
Mice[0].s=0;
for(i=1;i<k-1;i++)
{
Mice[i].s=0;
for(j=0;j<i;j++)
{
if(Mice[i].w>Mice[j].w) Mice[i].s=max(Mice[i].s,Mice[j].s+1);
}
if(len<Mice[i].s) len=Mice[i].s;
}
cout<<len+1<<endl;
int flag=k-1;//标记当前最大值的位置
int num[1001];
//从后向前找,从大到小找,然后倒序输出
for(i=len;i>=0;i--)
{
for(j=flag-1;j>=0;j--)
if(Mice[j].s==i) {num[i]=j;flag=j;break;}
}
for(i=0;i<=len;i++)//到序输出
{
cout<<Mice[num[i]].f<<endl;
}
return 0;
}
收获:
做DP的时候,观察DP的最终结果与前n项的联系,找出动态转移方程,从而求解。
另:愿姐姐生日快乐,3.8节快乐
分享到:
相关推荐
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
avr学习板,可以自己试着焊一块电路板,加深自己对avr的初步认识
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu题目分类
自己做的HDU ACM已经AC的题目