作者cutekid (可爱小孩子)
看板C_and_CPP
标题Re: [问题] 高中生解题系统B568一问
时间Wed Sep 12 21:26:45 2018
解法: 动态规划, 空间复杂度: 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://webptt.com/cn.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