Educational DP Contest A-J

A - Frog 1
思路：dp[i]: 青蛙跳到i位置最小cost，則動(dòng)規(guī)公式：dp[i] = min{dp[i-1]+|h_i-h_i-1|，注意
代碼：

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int MAXN = 10e5+10;

int N;
int h[MAXN];
int dp[MAXN];

int main() {
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> h[i];
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0; dp[2] = abs(h[1]-h[2]);
    for(int i=3; i<=N; i++) {
        dp[i] = min({dp[i], dp[i-1]+abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2])});
    }
    cout << dp[N] << endl;
    return 0;
}

B - Frog 2

思路：dp[i] = min{dp[i-j] + |h_i-h_j|}, 1<=j<=k
代碼：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 10e5+10;

int N, K;
int h[MAXN];
int dp[MAXN];

int main() {
    cin >> N >> K;
    for(int i=1; i<=N; i++) {
        cin >> h[i];
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0;
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=K; j++) {
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]));
        }
    }
    cout << dp[N] << endl;
    return 0;
}

C - Vacation

思路：dp[i][0]: 第i天選A獲得的最大幸福值
dp[i][0] = max{dp[i-1][1], dp[i-1][2]}+A[i],
dp[i][1] = max{dp[i-1][0], dp[i-1][2]}+B[i],
dp[i][2] = max{dp[i-1][0], dp[i-1][1]}+C[i],
ans = max{dp[N][0], dp[N][1], dp[N][2]}.
代碼：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5+10;
using ll = long long;

int N;
int a[MAXN], b[MAXN], c[MAXN];
ll dp[MAXN][4];
int main() {
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=N; i++) {
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i];
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i];
    }
    ll ans = 0; 
    for(int i=0; i<3; i++) {
        ans = max(ans, dp[N][i]);
    }
    cout << ans << endl;
    return 0;
}

D - Knapsack 1

E - Knapsack 2

思路：兩題都是經(jīng)典背包問(wèn)題废赞，區(qū)別在于D的W<10⁵而E的W<10⁹虎眨。設(shè)dp[i][j]: 前i個(gè)物品占j重量能獲得的最大價(jià)值，dp[i][j] = max{dp[i-1][j], dp[i-1][j-w[i]]+v[i]}祷安，發(fā)現(xiàn)dp[i][j]只跟dp[i-1]相關(guān)姥芥，因此可以去掉一維i把二維變一維。dp[j]:j重量所能獲得的最大價(jià)值汇鞭，dp[j] = max{dp[j], dp[j-w[i]]+v[i]}凉唐。但即便如此E還是會(huì)超時(shí)，因?yàn)閃太大10⁹必定超時(shí)霍骄。觀察V很小10³台囱，因此可以循環(huán)V，dp[j]:j價(jià)值所能獲得的最大重量读整，dp[j] = max{dp[j], dp[j-v[i]]+w[j]}簿训，循環(huán)時(shí)判斷如果dp[j]<W，記錄ans=max(ans, j)的值。
D代碼：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 110;
const int MAXW = 1e5+10;
using ll = long long;

struct item {
    int w, v;
};
item a[MAXN];
int N, W;
ll dp[MAXN][MAXW];
int main() {
    cin >> N >> W;
    for(int i=1; i<=N; i++) {
        cin >> a[i].w >> a[i].v;
    }
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=N; i++) {
        for(int j=0; j<=W; j++) {
            if(j-a[i].w<0) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i].w] + a[i].v);
        }
    }
    ll ans = 0;
    for(int j=1; j<=W; j++) {
        ans = max(ans, dp[N][j]);
    }
    cout << ans << endl;
    return 0;
}

E代碼：

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int MAXN = 110;
const ll MAXW = 1e9+10;
const int MAXV = 1e5+10;
struct item {
    ll w, v;
};
item a[MAXN];
int N, W;
ll dp[MAXV];
int main() {
    cin >> N >> W;
    ll s = 0;
    for(int i=1; i<=N; i++) {
        cin >> a[i].w >> a[i].v;
        s += a[i].v;
    }
    ll ans = 0;
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for(int i=1; i<=N; i++) {
        for(ll j=s; j>=a[i].v; j--) {
            dp[j] = min(dp[j], dp[j-a[i].v] + a[i].w);
            if(dp[j]<=W) ans = max(ans, j);
        }
    }
    /*
    for(int j=s; j>=0; j--) {
        if(dp[j]<=W)
            ans = max(ans, j);
    }
    */
    cout << ans << endl;
    return 0;
}

F - LCS

思路：經(jīng)典的最長(zhǎng)公共子序列强品，dp[i][j]: S1前i個(gè)字串和S2前j個(gè)字串的最長(zhǎng)公共子序列個(gè)數(shù)豺总。
$dp[i][j] = \begin{cases} dp[i-1][j-1]+1& \text{S1[i]==S2[j]} \\ max\{dp[i-1][j], dp[i][j-1]\}& \text{else} \\ \end{cases}$
題目不是求lcs的數(shù)量，而是lcs的字串序列择懂，因此需要輔助數(shù)組trace來(lái)記錄操作結(jié)果喻喳。
代碼：

#include<bits/stdc++.h>
using namespace std;

const int N = 3010;
string s, t;
int trace[N][N];
int dp[N][N];

int main() {
    cin >> s >> t;
    int n = s.length();
    int m = t.length();

    for(int i=0; i<=n; i++) {
        dp[i][0] = 0;
    }
    for(int j=0; j<=m; j++) {
        dp[0][j] = 0;
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(s[i-1]==t[j-1]) {
                trace[i][j] = 0;
                dp[i][j] = dp[i-1][j-1] + 1;
            }else {
                if(dp[i-1][j]>dp[i][j-1]) {
                    trace[i][j] = 1;
                    dp[i][j] = dp[i-1][j];
                }else {
                    trace[i][j] = 2;
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
    }
    string ans;
    while(n && m) {
//        printf("%d, %d : %d\n", n, m, trace[n][m]);
        if(trace[n][m] == 0) {
            ans.push_back(s[n-1]);
            --n; --m;
        }else if(trace[n][m] == 1) {
            --n;
        }else if(trace[n][m] == 2) {
            --m;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    
    return 0;
}
/*
// memorize dp
int lcs(int n, int m) {
    if(n==0 || m == 0) return 0;
    if(dp[n][m]) return dp[n][m];
    if(s[n-1] == t[m-1]) {
        trace[n][m] = 0;
        dp[n][m] = lcs(n-1, m-1)+1;
    }else {
        int a = lcs(n-1, m);
        int b = lcs(n, m-1);
//        printf("%d, %d : %d, %d\n", n, m, a, b);
        if(a>b) {
            dp[n][m] = a;
            trace[n][m] = 1;
        }else {
            dp[n][m] = b;
            trace[n][m] = 2;
        }
    }
    return dp[n][m];
}
int main() {
    cin >> s >> t;
    int n = s.length();
    int m = t.length();
    memset(dp, 0, sizeof(dp));
    lcs(n, m);
    string ans;
    while(n && m) {
//        printf("%d, %d : %d\n", n, m, trace[n][m]);
        if(trace[n][m] == 0) {
            ans.push_back(s[n-1]);
            --n; --m;
        }else if(trace[n][m] == 1) {
            --n;
        }else if(trace[n][m] == 2) {
            --m;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}
*/

G - Longest Path

思路：求圖的最長(zhǎng)路徑，最先想到枚舉每個(gè)頂點(diǎn)到其他頂點(diǎn)的路徑困曙，找最大值表伦，時(shí)間復(fù)雜度O(N*M)，按照題目給的10⁵肯定超時(shí)慷丽。其實(shí)很容易想到枚舉時(shí)必然有重復(fù)求解蹦哼，可以用memorized DP方法降低復(fù)雜度，最終復(fù)雜度O(N+M)要糊。
代碼：

#include<bits/stdc++.h>
using namespace std;

using LL = long long;
const int MAXN = 100100;

int N, M;
vector<int> g[MAXN];
int ans;
int dp[MAXN];
int dfs(int v) {
    if(dp[v]) return dp[v];
    for(int u=0; u<g[v].size(); u++) {
        dp[v] = max(dp[v], dfs(g[v][u])+1);
    }
    return dp[v];
}
int main() {
    scanf("%d%d", &N, &M);
    for(int i=0; i<M; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
    }
    
    memset(dp, 0, sizeof(dp));
    ans = 0;
    for(int i=1; i<=N; i++) {
        ans = max(ans, dfs(i));
    }
    printf("%d\n", ans);
    return 0;
}

H - Grid 1

題目大意：求迷宮中從左上角到右下角路徑個(gè)數(shù)纲熏。
思路：dp[x][y] = dp[x-1][y] + dp[x][y-1]
代碼：

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
#define MAXH 1010
#define MAXW 1010
const int MOD = 1e9+7;

int H, W;
char g[MAXH][MAXW];

int dx[] = {1, 0};
int dy[] = {0, 1};
int dp[MAXH][MAXW];

void debug() {
    for(int i=1; i<=H; i++) {
        for(int j=1; j<=W; j++) {
            cout << dp[i][j];
        }
        cout << endl;
    }
}
int main() {
    cin >> H >> W;
    for(int i=1; i<=H; i++) {
        for(int j=1; j<=W; j++) {
            cin >> g[i][j];
        }
    }

    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=H; i++) {
        for(int j=1; j<=W; j++) {
            if(i==1&&j==1){
                dp[i][j] = 1;
                continue;
            }
            if(g[i][j] == '#')
                dp[i][j] = 0;
            else
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
        }
    }
    cout << dp[H][W] << endl;
//    debug();
    return 0;
}

I - Coins

思路：dp[i][j]: 擲前i個(gè)硬幣有j個(gè)面朝上的概率，則dp[i][j] = dp[i-1][j-1]*p_j + dp[i-1][j]*(1-p_j)锄俄，最后 $\sum_{k=\lceil N/2 \rceil}^{N} {dp[N][k]}$ .
代碼：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 3010;
using ll = long long;

int N;
double p[MAXN];
// dp[i][j]: 前i個(gè)硬幣j個(gè)頭朝上的概率
double dp[MAXN][MAXN];

int main() {
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> p[i];
    }

    dp[0][0] = 1; 
    for(int i=1; i<=N; i++) {
        for(int j=0; j<=i; j++) {
            if(j) dp[i][j] += dp[i-1][j-1]*p[i];
            dp[i][j] += dp[i-1][j] * (1-p[i]);
        }
    }
    double ans = 0.0;
    for(int i=(N+1)/2; i<=N; i++) {
        ans += dp[N][i];
    }
    cout <<setprecision(10) << ans << endl;
    return 0;
}

J - Sushi

題目大意：有N個(gè)dishes局劲，每個(gè)dish有1~3個(gè)sushi，求拿走所有sushi的操作期望值奶赠。
思路：dp狀態(tài)的個(gè)數(shù)肯定不能選N鱼填，猜測(cè)3個(gè)狀態(tài)x、y毅戈、z苹丸。x代表1個(gè)sushi的盤子個(gè)數(shù)，y代表2個(gè)sushi的盤子個(gè)數(shù)苇经，z代表3個(gè)sushi的盤子個(gè)數(shù)赘理，設(shè)dp(x, y, z)為當(dāng)1個(gè)sushi的盤子有x個(gè)，2個(gè)sushi的盤子有y個(gè)，3個(gè)sushi的盤子有z個(gè)時(shí)操作期望值，則dp(x,y,z) = x/n * dp(x-1, y, z) + y/n * dp(x+1, y-1, z) + z/n * dp(x, y+1, z-1) + (n-x-y-z)/n * dp(x, y, z) + 1，共同項(xiàng)dp(x,y,z)移項(xiàng)后化簡(jiǎn)得到：dp(x,y,z)=x/(x+y+z)dp(x-1,y,z) + y/(x+y+z)dp(x+1,y-1,z) + z/(x+y+z)*dp(x,y+1,z-1) + n/(x+y+z)
代碼：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 310;
int N;
int a[MAXN];
double dp[MAXN][MAXN][MAXN];

int cnt[4];

double solve(int x, int y, int z) {
    double ret;
    if(x==0 && y==0 && z==0) return 0;
    if(dp[x][y][z]>0.0) return dp[x][y][z];
    int sum = x+y+z;
    ret = 1.0*N/sum;
    if(x>0) {
        ret += 1.0*x/sum * solve(x-1, y, z);
    }
    if(y>0) {
        ret += 1.0*y/sum * solve(x+1, y-1, z);
    }
    if(z>0) {
        ret += 1.0*z/sum * solve(x, y+1, z-1);
    }
    return dp[x][y][z] = ret;
}
int main() {
    cin >> N;
    memset(cnt, 0, sizeof(cnt));
    for(int i=1; i<=N; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    cout <<fixed<<setprecision(14) <<solve(cnt[1], cnt[2], cnt[3]) << endl;
    return 0;
}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市掏父，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌渺氧，老刑警劉巖洞渔，帶你破解...
沈念sama閱讀 211,743評(píng)論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異稽寒，居然都是意外死亡扮碧，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,296評(píng)論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)慎王，“玉大人蚓土，你說(shuō)我怎么就攤上這事±涤伲” “怎么了蜀漆？”我有些...
開(kāi)封第一講書(shū)人閱讀 157,285評(píng)論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)咱旱。經(jīng)常有香客問(wèn)我确丢，道長(zhǎng)，這世上最難降的妖魔是什么吐限？我笑而不...
開(kāi)封第一講書(shū)人閱讀 56,485評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任鲜侥，我火速辦了婚禮，結(jié)果婚禮上诸典，老公的妹妹穿的比我還像新娘描函。我一直安慰自己，他們只是感情好狐粱，可當(dāng)我...
茶點(diǎn)故事閱讀 65,581評(píng)論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布舀寓。她就那樣靜靜地躺著，像睡著了一般肌蜻。火紅的嫁衣襯著肌膚如雪基公。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書(shū)人閱讀 49,821評(píng)論 1贊 290
城市分裂傳說(shuō)
那天宋欺，我揣著相機(jī)與錄音轰豆，去河邊找鬼。笑死齿诞，一個(gè)胖子當(dāng)著我的面吹牛酸休，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播祷杈，決...
沈念sama閱讀 38,960評(píng)論 3贊 408
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼斑司，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了但汞？” 一聲冷哼從身側(cè)響起宿刮，我...
開(kāi)封第一講書(shū)人閱讀 37,719評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎私蕾，沒(méi)想到半個(gè)月后僵缺，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,186評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡踩叭，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,516評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年磕潮，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了翠胰。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,650評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡自脯，死狀恐怖之景，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情膏潮，我是刑警寧澤锻狗，帶...
沈念sama閱讀 34,329評(píng)論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站焕参，受9級(jí)特大地震影響轻纪，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜龟糕，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,936評(píng)論 3贊 313
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一桐磁、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧讲岁，春花似錦我擂、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,757評(píng)論 0贊 21
一樁弒父案校摩，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至阶淘，卻和暖如春衙吩，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背溪窒。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 31,991評(píng)論 1贊 266
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工坤塞，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人澈蚌。一個(gè)月前我還...
沈念sama閱讀 46,370評(píng)論 2贊 360
代替公主和親
正文我出身青樓摹芙，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親宛瞄。傳聞我的和親對(duì)象是個(gè)殘疾皇子浮禾，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,527評(píng)論 2贊 349