A – LIS O(n^2) 模板 B – 一维线性dp ++ HDU – 2059 dp接触的太少,找了几个题一维dp的题,跟大家一下 HDU C – Frog Jumping CodeForces – 1077A 题目链接 https://poj.org/problem?id=3278 D – Disturbed People CodeForces – 1077B E – Good Array CodeForces – 1077C 未完待续。。。。。。
最长上升子序列,两种做法
1,O(n^2) 两层循环,依次遍历
2,O(nlogn) 一层循环,用二分#include<stdio.h> #include<algorithm> using namespace std; const int maxx=100019; int a[10109],ans[10109]; int main() { int i,j,n; scanf("%d",&n); for(i=1; i<=n; i++) { scanf("%d",&a[i]);ans[i]=1; } for(i=2; i<=n; i++) { for(j=1; j<i; j++) { if(a[i]>a[j]) ans[i]=max(ans[i],ans[j]+1); } } sort(ans+1,ans+1+n); printf("%dn",ans[n]); return 0; }
dp到达每个充电站的最短时间(类似第一题,只是判断的条件不同),一个小细节是最开始的时候车子有电,相当于充电了,但不能算时间
一开始有个疑惑:到达一个充电站后车子可能还有电,下一段会先高速行驶啊?
这里是包括这种情况的,假设到第Pn个充电站了还有电,但我们在遍历第Pn-1个充电站时,会先以高速行驶C米到达当前dp点,这样就 包含了上面的问题(状态转移的巧妙)
1087 1257 1003 1800 1025 1160 2517 3998 #include<stdio.h> int p[102]; double dp[102]; int main() { int i,j,l,n,c,t,vr,v1,v2,len; double min,e; while(scanf("%d",&l)!=EOF) { scanf("%d%d%d%d%d%d",&n,&c,&t,&vr,&v1,&v2); dp[0]=p[0]=0; for(i=1; i<=n; i++) scanf("%d",&p[i]); p[i]=l; for(i=1; i<n+2; i++) { min=999999999; for(j=0; j<i; j++) { len=p[i]-p[j]; if(len>c) e=1.0*c/v1+(len-c+0.)/v2; else e=1.0*len/v1; e+=dp[j]; if(j) e+=t; if(min>e) min=e; } dp[i]=min; } if(1.0*l/vr>dp[n+1]) printf("What a pity rabbit!n"); else printf("Good job,rabbit!n"); } }
由于向左与向右是交替的,所以向左和向右两次看作一组运动,判断k的奇偶性再相加减即可。
(突然想到一个题,也是在坐标轴上跳,队列的一个经典题)#include<bits/stdc++.h> using namespace std; #define ll long long const int maxx=300019; int main() { ll a,b,k,t; scanf("%lld",&t); while(t--) { scanf("%lld%lld%lld",&a,&b,&k); if(k%2==0) { printf("%lldn",(a-b)*(k/2)); } else { printf("%lldn",(a-b)*(k/2)+a); } } return 0; }
直接遍历模拟一下即可,符合条件的时候要把后方的灯关掉#include <bits/stdc++.h> using namespace std; const int maxx=100017; int a[100]; int main() { int i,n,ans=0; scanf("%d",&n); for(i=1; i<=n; i++) scanf("%d",&a[i]); for(i=2; i<n; i++) { if(a[i]==0&&a[i-1]==1&&a[i+1]==1) { ans++; a[i+1]=0; } } printf("%dn",ans); return 0; }
首先找到数组的最大值和第二大的值,然后遍历数组,判断是否是最大值值分两种情况讨论,开个数组储存符合题意的下标,最后输出即可。#include <bits/stdc++.h> using namespace std; #define ll long long const int maxx=200017; ll a[maxx],b[maxx]; int pos=0; ll ans[maxx]; int main() { ll i,n,sum=0; scanf("%lld",&n); for(i=1; i<=n; i++) { scanf("%d",&a[i]); b[i]=a[i]; sum+=a[i]; } sort(b+1,b+1+n); for(i=1; i<=n; i++) { if(a[i]==b[n]) { if(b[n-1]*2==(sum-b[n])) { ans[++pos]=i; } } else { if(b[n]*2==(sum-a[i])) { ans[++pos]=i; } } } printf("%dn",pos); if(pos>=1) printf("%lld",ans[1]); for(i=2; i<=pos; i++) printf(" %lld",ans[i]); return 0; }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)