Zutround 6 部分题题解网络weixin45705885的博客-

A – LIS O(n^2) 模板
  最长上升子序列，两种做法
    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; } 

B – 一维线性dp ++ HDU – 2059
  dp到达每个充电站的最短时间(类似第一题，只是判断的条件不同)，一个小细节是最开始的时候车子有电，相当于充电了，但不能算时间
  一开始有个疑惑：到达一个充电站后车子可能还有电，下一段会先高速行驶啊？
这里是包括这种情况的，假设到第Pn个充电站了还有电，但我们在遍历第Pn-1个充电站时，会先以高速行驶C米到达当前dp点，这样就 包含了上面的问题（状态转移的巧妙）

dp接触的太少，找了几个题一维dp的题，跟大家一下

HDU
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"); } } 

C – Frog Jumping CodeForces – 1077A
   由于向左与向右是交替的，所以向左和向右两次看作一组运动，判断k的奇偶性再相加减即可。
（突然想到一个题，也是在坐标轴上跳，队列的一个经典题）

题目链接  https://poj.org/problem?id=3278

#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; } 

D – Disturbed People CodeForces – 1077B
  直接遍历模拟一下即可，符合条件的时候要把后方的灯关掉

#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; } 

E – Good Array CodeForces – 1077C
  首先找到数组的最大值和第二大的值，然后遍历数组，判断是否是最大值值分两种情况讨论，开个数组储存符合题意的下标，最后输出即可。

#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; } 

未完待续。。。。。。