Super Jumping! Jumping! Jumping! HDU - 1087
这题错的莫名其妙
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAXN 1000+5
using namespace std;
int a[1005];
int dp[1005];
int main(void)
{
intn;
while((scanf("%d",&n))==1&&n)
{
for(inti=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i]=a[i];
}
for(inti=2;i<=n;i++)
{
intmmax=-99999;
for(intj=1;j<i;j++)
{
if(a[j]<a[i]&& a[j] >= mmax)
{
mmax= a[j];
}
}
//printf("%d-",index);
if(index!=-1)
dp[i]+=dp[index];
//printf("%d-",dp[i]);
}
int mmax=-999999;
for(inti=1;i<=n;i++)
{
if(dp[i]>mmax)
mmax=dp[i];
}
printf("----%d\n",mmax);
}
}
AC了，发现还是思维错了，求的应该是 a[i] < a[i] 中 DP 最大的 ，而不是 a[j] < a[i] 中，，最大的数，， 对应的 DP 。 比如例子 7 1 2 3 4 5 6 8 如果按照上面的会输出 15 ，然而应该是 1+2+3+4+5+6+8 是最大值 。 这题可以简单的说，我只要找出比 a [i] 小的d[j]集合中 ， dp最大的那个 。。 必定满足每次都是最大，那么dp[1~n] 每一个都是最优的情况，那么推出 dp[n]就是最优的情况. 就满足了最优子解的问题。再者考虑 无后效性 ， 前面我选择了什么，只能通过当前的状态去影响后面的状态，而不能持续的影响以后的状态， 我通过哪个dp 找到当前的 dp[i] 无所谓（4 3 1 5，DP[4]无论是从4→5还是3→1→5，对于5后面的DP没有任何影响），我只要找到DP最大的，并且小于a[i]的就满足要求就可以。 ````````` 也就这么粗浅的理解了，还需要多做题来理解题目意思`````。动态规划就是说要求 每一个DP 都是 最优，每一个DP都是由前面的最优DP推出来，当前的求得的DP由前面最优的DP求出来，当前的DP也就是最优的，每一个DP是最优的，最终所求的DP[N]就是最优解了1！！！！！。 这题和最长上升序列几乎一样
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 1000+5
using namespacestd;
int a[10005];
int dp[10005];
int main(void)
{
int n;
while((scanf("%d",&n))==1&&n)
{
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i]=a[i];
}
dp[1]=a[1];
for(int i=2;i<=n;i++)
{
int mmax=0;
int index=-1;
for(int j=1;j<i;j++)
{
if(a[j]<a[i] && dp[j]>= mmax)
{
mmax = dp[j];
index = j;
}
}
//printf("%d-",index);
dp[i]+=mmax;
//printf("%d-",dp[i]);
}
int mmax=-999999;
for(int i=1;i<=n;i++)
{
//printf("%d-",dp[i]);
if(dp[i]>mmax)
mmax=dp[i];
}
printf("%d\n",mmax);
}
}
