啊哈哈今天又是模拟赛
然而比利A掉了第二道 我只打了3题暴力……
然后发现第二道是签到题
调LCT调得日狗……先去做几道水题愉♂悦身心
第一眼我觉得是个先排序然后$N^2$DP的大水题
从后往前做，$dp_{i,j}$ 表示以 $a_i$ 为第一个, $a_j$ 为第二个的最长Fibonacci数列……
然后打完一看卧槽还有负数日狗了
然后就不会做了……然后看了题解
题解说暴力就行了 枚举开头两个暴力往下跑
因为Fibonacci在题目这个范围内最多90项……
虽然还是大水题但是的确让我有点蛋疼
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=1005;
int n,a[N],b[N],c[N],cnt;
int DFS(int x,int y){
int z=x+y,pos=lower_bound(b+1,b+cnt+1,z)-b;
if (pos==cnt+1||b[pos]!=z||!c[pos]) return 0;
else{
c[pos]--;
int ret=DFS(y,z)+1;
c[pos]++;return ret;
}
}
int main(){
n=IN();
Rep(i,1,n) a[i]=IN();
sort(a+1,a+n+1);
b[1]=a[1],cnt=c[1]=1;
Rep(i,2,n){
if (a[i]==a[i-1]) c[cnt]++;
else b[++cnt]=a[i],c[cnt]=1;
}
int Ans=0;
Rep(i,1,cnt) if (b[i]==0) Ans=c[i];
Rep(i,1,cnt) Rep(j,1,cnt){
if (b[i]==0&&b[j]==0) continue;
if (i==j&&c[i]<2) continue;
c[i]--,c[j]--;
Ans=max(Ans,DFS(b[i],b[j])+2);
c[i]++,c[j]++;
}
printf("%d\n",Ans);
}
发现自己一直不会斜率优化DP……
然后就去做了一下这道入门题
具体的请戳右边→点我点我
注意是多组数据！
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=500005;
ll pre[N],f[N];
int q[N],n,m;
ll X(int i,int j){
return (pre[i]-pre[j])*2;
}
ll Y(int i,int j){
return f[i]+pre[i]*pre[i]-f[j]-pre[j]*pre[j];
}
ll Val(int i,int j){
return f[j]+(pre[i]-pre[j])*(pre[i]-pre[j])+m;
}
int main(){
while (~scanf("%d%d",&n,&m)){
pre[0]=0,f[0]=0;
Rep(i,1,n){int x=IN();pre[i]=pre[i-1]+x;}
int h=1,t=1;
q[1]=0;
Rep(i,1,n){
while (h<t&&Y(q[h+1],q[h])<=pre[i]*X(q[h+1],q[h])) h++;
f[i]=Val(i,q[h]);
while (t>h&&Y(i,q[t])*X(q[t],q[t-1])<=Y(q[t],q[t-1])*X(i,q[t])) t--;
q[++t]=i;
}
printf("%I64d\n",f[n]);
}
}
Jan 25, 2024 02:51:29 PM
Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.