DPと思いきやメモ化じゃないと…

日付タイトルが気になる方はメインブログに行ってください。
さて、今日部活で解いた(?)もの

3181

多倍長+DP
DP自体はすごい簡単なんだけれども多倍長との兼ね合いが難しい感じの問題。
多倍長わかんなーいとかほざいてたりしてたら結局写経になってしまったのだけれども…
ちなみに多倍長にすると速度とかいろんな都合上メモ化のほうが書きやすい。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, k;
char* add(char* a, char* b, char* out) {
    int as=strlen(a), bs=strlen(b);
    int c=0;
    int sz=0;
    for (int i=0; i<(as<bs?bs:as); i++) {
        int t=c;
        if (i<as) t+=a[i]-'0';
        if (i<bs) t+=b[i]-'0';
        c=t/10;
        t%=10;
        out[sz++]=t+'0';
    }
    if (c) out[sz++]=c+'0';
    out[sz]=0;
    return out;
}
char dp[1001][101][40];
bool vis[1001][101];
char zero[]="0";
char one[]="1";
char* rec(int n, int k) {
    if (n<0||k<1) return zero;
    if (n==0) return one;
    if (vis[n][k]) return dp[n][k];
    vis[n][k]=true;
    return add(rec(n,k-1),rec(n-k,k),dp[n][k]);
}
int main() {
    scanf("%d%d", &n, &k);
    string ans(rec(n,k));
    reverse(ans.begin(), ans.end());
    cout<<ans<<endl;
}

3186

単純に考えたら蟻本に載っている貪欲問題と同じはずなんだけどそれだと間違えなので残っている範囲でDPする
DPするといっても順番が特殊だからやっぱりメモ化が簡単

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, v[2000];
ll dp[2001][2001];
ll solve(int f, int t) {
    int len=n-(t-f-1);
    if (dp[f][t]) return dp[f][t];
    if (len==n) return n*v[f];
    return dp[f][t]=max(solve(f+1,t)+len*v[f],solve(f,t-1)+len*v[t-1]);
}
int main() {
    scanf("%d",&n);
    for (int i=0; i<n; i++) scanf("%d",&v[i]);
    printf("%lld\n",solve(0,n));
}