动态规划基础(函数的定义) 洛谷原创题

前言

帮群友随手写写的

题目描述

数据范围

• $10^4>y>x>1$

解题思路

动态规划

对于这类问题，我们可以使用递归解决，设$dfs(i,j)$，其中$i=x$，$j=y$

根据题意得

• 当$x>1$，$dfs(i,j)=y+dfs(i-1,j-1)$
• 当$x=1$，$dfs(i,j)=y$

这样我们就可以写一个递归了 这里我为了方便 所以用python

def dfs(i,j):
    if i == 1:
        return j
    else:
        return j+dfs(i-1,j-1)

## test
x = 2
y = 3
print(dfs(x,y))

x = 1
y = 4
print(dfs(x,y))

这里是不用记忆化搜索的，因为递归的过程中并没有重复计算

现在我们来1:1翻译成递推

dp[i][j] = j+dp[i-1][j-1]
dp[i][j] = j

我们可以看到，如果直接从0开始遍历 会出现负数下标 因此我们可以+1则变成

dp[i+1][j+1] = j+dp[i][j]
dp[i+1][j+1] = j

由于题目已给$10^4>x>y>1$，所以递归和二维dp是过不了本题的

得考虑状压dp，可以把他压缩成一维dp

这里的状态转移主要是j 因此可以缩写成

$$dp[i+1] = i$$

dp代码

Python

dp = [0 for _ in range(10002)]
def dfs(x,y):
    for i in range(1,y+1): # 注意要+1
        dp[i+1] = i
    return sum(dp[y+2-x:y+2])


## test
x = 2
y = 3
print(dfs(x,y))

x = 1
y = 4
print(dfs(x,y))

C++

int dp[10002];
int dfs(int x,int y){
    for(int i = 1; i <= y;i++){
        dp[i+1] = i;
    }
    int ans = 0;
    for(int i = y+2-x; i<=y+2;i++){
        ans+=dp[i];
    }
    return ans
}


int main() {
    int x = 2;
    int y = 3;
    cout<<dfs(x,y)<<endl;
    
    x = 1;
    y = 4;
    cout<<dfs(x,y);
    
    return 0;
}

数学

这里就要开始分析了，假设$x=2,y=3$

从代码执行的角度来看无非是，$3+dfs(2-1,3-1)$，实际发生的计算为$3+2$

同样的道理，当$x=1,y=4$时，实际发生计算为$4$

总结出一个规律，首先是

$$(y-1)+(y-1-1)+(y-1-1)+...$$

终止条件为$x=1$

但是这样做，好想有点难思考

我们可以先吧$0+1+2+3....+y$算出来，再减去$0+1+2+3...+x$

这里的计算，可以套用我博客的之前的公式，详情请看->点我

$$ans=\begin{cases} i*k+(k-1)*(k//2) & k/2=0 \\ i*k+(k-1)*(k//2)+(k//2) & k/2!=0\end{cases}$$

把这里的$k$，换成$x$和$y$就行了，同时$i=1$，$ans=(y-x,y)$

def ans(x,y):
    o = 0;p = 0;
    if x % 2 == 0:
        o = 1*x+(x-1)*(x//2)
    else:
        o = 1*x+(x-1)*(x//2)+(x//2)
    if y % 2 == 0:
        p = 1*y+(y-1)*(y//2)
    else:
        p = 1*y+(y-1)*(y//2)+(y//2)
    return p-o


x = 2
y = 3
print(ans(y-x,y))

x = 1
y = 4
print(ans(y-x,y))

数学代码

Python3

def ans(x,y):
    o = 0;p = 0;
    if x % 2 == 0:
        o = 1*x+(x-1)*(x//2)
    else:
        o = 1*x+(x-1)*(x//2)+(x//2)
    if y % 2 == 0:
        p = 1*y+(y-1)*(y//2)
    else:
        p = 1*y+(y-1)*(y//2)+(y//2)
    return p-o


x = 2
y = 3
print(ans(y-x,y))

x = 1
y = 4
print(ans(y-x,y))

C++

int ans(int x,int y){
    int o = 0;
    int p = 0;
    if(o%2==0){o = 1*x+(x-1)*(x/2);}
    else{o = o = 1*x+(x-1)*(x/2)+(x/2);}
    
    if(y%2==0){p = 1*y+(y-1)*(y/2);}else{p=1*y+(y-1)*(y/2)+(y/2);}
    return p-o;
}


int main() {
    int x = 999;
    int y = 1000;
    cout<<ans(y-x,y)<<endl;
    
    x = 1;
    y = 4;
    cout<<ans(y-x,y);
    
    return 0;
}

后记

喜欢的话，多多支持，同时也关注一下我