【JZOJ】【DP】NIKOLA

NIKOLA

（AK L（了） NOI）

有$n$个方格，原始在第一格，第一轮将会由第一格跳到第二格，接下来每轮有两个操作：
一、向前跳：比之前跳的距离远一格
二、向后跳：与之前跳的距离一样远
每一个格子要想应得数值，刚“出生”不用加第一格的数值
求跳到$n$个格子时最小值为多少

输入

样例输入

6 
1 
2 
3 
4 
5 
6 

输出

样例输出

12

思路

DP
$f[i][j]$代表经过$i$个格子跳到第$j$个格子的最小值

#include
#include
#include
using namespace std;
int a[20025],f[2005][2005];
int n,ans=1e9;
int main()
{memset(f,127,sizeof(f));scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);f[0][1]=0;for(int i=1;i<=n;++i){for(int j=n;j>=1;j--){f[i][j]=min(f[i][j],f[i][i+j]+a[j]);f[i][j]=min(f[i][j],f[i-1][j-i]+a[j]);}ans=min(ans,f[i][n]);}printf("%d",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！