Zut_round 6 部分题题解
A - LIS O(n^2) 模板
最长上升子序列，两种做法
1，O(n^2) 两层循环，依次遍历
2，O(nlogn) 一层循环，用二分
#include
#include
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; ja[j])
ans[i]=max(ans[i],ans[j]+1);
}
}
sort(ans+1,ans+1+n);
printf("%d\n",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
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; jc)
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的奇偶性再相加减即可。
（突然想到一个题，也是在坐标轴上跳，队列的一个经典题）
题目链接 http://poj.org/problem?id=3278
#include
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("%lld\n",(a-b)*(k/2));
}
else
{
printf("%lld\n",(a-b)*(k/2)+a);
}
}
return 0;
}
D - Disturbed People CodeForces - 1077B
直接遍历模拟一下即可，符合条件的时候要把后方的灯关掉
#include
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("%d\n",ans);
return 0;
}
E - Good Array CodeForces - 1077C
首先找到数组的最大值和第二大的值，然后遍历数组，判断是否是最大值值分两种情况讨论，开个数组储存符合题意的下标，最后输出即可。
#include
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=1)
printf("%lld",ans[1]);
for(i=2; i<=pos; i++)
printf(" %lld",ans[i]);
return 0;
}
未完待续。。。。。。
作者：weixin_45705885
