首页 > 代码库 > Gym 100090M Jumping along the Hummocks
Gym 100090M Jumping along the Hummocks
题意：
从 前往后跳，要么跳一步，跳到相邻的位置，要么跳到下一个数字相同的位置，求跳到最后的最少步数。
dp，但是会tle，我用map优化了一下。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 6 const int inf = 0x3f3f3f3f; 7 int a[200005]; 8 int dp[200005]; 9 10 int main() {11 12 int n;13 while(~scanf("%d",&n)) {14 for(int i=0;i<n;i++) {15 scanf("%d",&a[i]);16 }17 18 memset(dp,inf,sizeof(dp));19 dp[0] = 0;20 map<int,int> maps;21 maps[a[0]] = 0;22 for(int i=1;i<n;i++) {23 dp[i] = dp[i-1] + 1;24 if(maps.count(a[i])>0) {25 dp[i] = min(dp[i],maps[a[i]] + 1);26 maps[a[i]] = dp[i];27 }28 else {29 maps[a[i]] = dp[i];30 }31 }32 printf("%d\n",dp[n-1]);33 34 }35 36 return 0;37 }
Gym 100090M Jumping along the Hummocks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。