月份: 2021 年 6 月

C++ 動態規劃經典題 01 背包 (atcoder)

mtmattC++基本題(解題系統)Leave a Comment on C++ 動態規劃經典題 01 背包 (atcoder) 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[105][100010],v[105],w[105];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int n,W;
    cin>>n>>W;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=W;j++){
            if(w[i]>j) dp[i][j]=dp[i-1][j];
            else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            }
        }
    }
    cout<<dp[n][W];
    return 0; 
}

前提是n*W不能太大。

106 台中區資訊學科能力競賽試題 總結

mtmatt競賽題Leave a Comment on 106 台中區資訊學科能力競賽試題 總結

第一題到第五題都非常簡單，但第六題與第七題的難度與前五題根本不是一個量級，第六題用到回朔DFS，第七題是DP。而前五題卻不需要演算法。總歸一句：資訊學科能力競賽試題仍然是值得練習的題目。還有，我該練動態規劃啦！

題解連結：

  1. https://mtmatt.page/contest/c-tj-106-1/
  2. https://mtmatt.page/contest/c-tj-106-2/
  3. https://mtmatt.page/contest/c-tj-106-3/
  4. https://mtmatt.page/contest/c-tj-106-4/
  5. https://mtmatt.page/contest/c-tj-106-5/
  6. https://mtmatt.page/contest/c-tj-106-6/
  7. https://mtmatt.page/contest/c-tj-106-7/

C++ 台中區 106-7 雙層骨牌

mtmatt競賽題Leave a Comment on C++ 台中區 106-7 雙層骨牌

這題就難了，我真的想不到O(q2)以內的解。有點像01背包，就先參考別人的程式碼，並從中學習吧！(不是複製喔)

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define INF 32000

int q,d;
short dp[1005][12010];

int main(){
    cin>>q;
    int up,dw;
    for(int i=0;i<1050;i++){
        for(int j=0;j<12010;j++) dp[i][j]=INF;
    }
    
    const int mx=6*q;
    dp[0][mx]=0;
    for(int i=1;i<=q;i++){
        cin>>up>>dw;
        d=up-dw;
        for(int j=mx-i*6;j<=mx+i*6;j++){
            dp[i][j]=min(dp[i-1][j-d],dp[i-1][j+d]+1);
        }
    }
    
    int k=mx;
    while(dp[q][k]==INF) k++;
    cout<<dp[q][k]<<"\n"<<k-mx;
    return 0;
}

出處：http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=d091
參考：https://www.itread01.com/content/1545447844.html