作者cateran (雲川閒步)
看板C_and_CPP
標題Re: [問題] 高中生解題系統B568一問
時間Fri Sep 14 12:19:00 2018
※ 引述《cutekid (可愛小孩子)》之銘言：
解法: 動態規劃, 空間複雜度: 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;
}
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.168.23.228
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1536758808.A.996.html
1F：推 sarafciel: 簡單明瞭 推 09/13 09:07
2F：推 Ori185: 不好意思 菜逼八是我其實看了很久還是不懂… 09/13 23:42
3F：→ Ori185: 請問可以提示一點code的方向讓我推論嗎？ 09/13 23:43
4F：推 alan23273850: 還沒消化先給推 09/14 00:18
其實邏輯很簡單 甚至有點暴力 就是把所有可能的數字和 都標記在dp陣列裡面
因為題目上限七十萬 所以數字和不會爆掉
dp[i] != 0 表示i是一個可能的解(數字和)
他很巧妙的在迴圈中用dp[i]的值標記這是新加入的數字 避免重複計算
最後從dp[MAX]倒著看回來 第一個非0的陣列index就是答案
話說這個解法在系統上是50ms左右的時間
看排行榜還有一堆4ms的 就不知道是什麼神奇解法了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 100.0.196.193
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1536898744.A.146.html
※ 編輯: cateran (100.0.196.193), 09/14/2018 12:23:40
5F：推 cutekid: 推，解釋的真好(Y) 09/14 13:56
6F：推 Ori185: 非常感謝，小弟終於看懂了，覺得有夠感動XD 09/14 18:40
7F：推 alan23273850: 其實我蠻好奇在打 code 之前要怎麼確定 700000*n 的 09/15 15:48
8F：→ alan23273850: 時間複雜度不會超過上限，畢竟看到 700000 大概就先 09/15 15:49
9F：→ alan23273850: 倒退三步了吧，哪有心情想算法 09/15 15:49
10F：→ alan23273850: 剛剛也看懂了，心情真舒爽 09/15 15:55
11F：推 idiont: 以我自己過往的經驗 不考慮常數的話 10^8會當作1秒 09/15 16:18
12F：→ idiont: 不過judge的機器可能很好 10^9也不會TLE 09/15 16:19