Re: [問題] 高中生解題系統B568一問
解法: 動態規劃, 空間複雜度: 700,000, 時間複雜度: 700,000 x n(題目)
以下程式碼(約20行):
#include<stdio.h>
#define MAX 700000
int main(){
int i,k,n,v;
char dp[MAX + 1] = {0};
for(scanf("%d",&n); scanf("%d",&k) != EOF; --n){
for(i = 1; i <= MAX; ++i){
if(dp[i] && dp[i] != n){
v = (i + k - 1) % MAX + 1;
if(!dp[v]) dp[v] = n;
}
else if(i == k) dp[i] = n;
}
}
for(i = MAX;!dp[i];--i);
printf("%d\n",i);
return 0;
}
※ 引述《Ori185 (Ori185)》之銘言：
: 開發平台(Platform): (Ex: Win10, Linux, ...)
: WIN10
: 編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
: g++
: 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
: 問題(Question)：
: https://zerojudge.tw/ShowProblem？problemid=b568
: 小弟我目前剛學到動態規劃演算法
: 看到這題似乎可以應用到便試了試
: 結果從第三個測資開始似乎因為超過限制的64MB而終止
: 認為應該有比起創立一個超級大的二維陣列以外(70萬…)
: 更加節省空間聰明的辦法
: 請問可以指點解一下嗎？
: 非常謝謝
: 程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔)
: https://glot.io/snippets/f4odl8o9kh/raw
: 補充說明(Supplement)：
: 記憶體限制64MB
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.168.23.228
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1536758808.A.996.html
推
09/13 09:07,
7年前
, 1F
09/13 09:07, 1F
推
09/13 23:42,
7年前
, 2F
09/13 23:42, 2F
→
09/13 23:43,
7年前
, 3F
09/13 23:43, 3F
推
09/14 00:18,
7年前
, 4F
09/14 00:18, 4F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章