hdu 1087スーパージャンプ!ジャンプジャンプ(最長上昇サブシーケンス&dp)

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=1087
実はこのような問題の解決の核心は最大上昇サブシーケンスと呼ぶべきだと思います.単純な長さではなく、一番長いです.試験用例を導入することによって、3 1 3 2 4 4 3 1 2 1 7 1 3 2 5 4 4 4 4 4 1 2 3 3 3 3 3 3 3 3 3 3 3 1 4 4 4 4 1 1 2 3 3 0ダイナミック企画の考え方で解決します.

#include <iostream>
#include<cstdio>
using namespace std;
long long f[1005],inp[1005];
int main(int argc, char *argv[]) {
    //freopen("cin.txt","r",stdin);
    int n,i,j;
    long long t;
    while(cin>>n&&n){
        for(i=0;i<n;i++){
            scanf("%lld",&f[i]);
            inp[i]=f[i];
        }
        for(j=1;j<n;j++){
            t=f[j];
            for(i=0;i<j;i++){
                if(f[i]<f[j]&&t+inp[i]>inp[j])inp[j]=t+inp[i];
            }
        }
        long long ans=inp[0];
        for(i=1;i<n;i++)ans=ans>inp[i]?ans:inp[i];
        printf("%lld
",ans);
    }
    return 0;
}

出力結果:
4
10
3
15
9