[DP][复杂度分析] Gym – 101485D Debugging

有趣的一道dp,让我想起了msc面试的时候问的扔杯子的问题。

首先,如果确定了对于长度为n的代码要写x个printf,那么这x个一定是尽量均匀分布(数学显然)才能使得最坏情况最好!因此,可以写出递推式:f(n)=min(f(ceil(1.0*n/i))+r+i*p);记忆化搜索暴力转移即可。

这个复杂度分析很数学:[n/i]的只有O(sqrt(n))种可能,每种可能的情况递归下去的话[n/ab]=[[n/a]/b],仍然是在那sqrt(n)种可能里面。所以总共有sqrt(n)个点会往下递归,每个递归点又最多有sqrt(n)次,相乘的话相当于O(n);

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=1e6+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

LL vis[maxn],r,p;
LL dp(int n)
{
    if(~vis[n])
        return vis[n];
    if(n<=1)
        return vis[n]=0;
    LL ans=(1LL<<60);
    for (int i=1;i
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据