DAY1 AC率 6/1 185

小田的宝石镇

思路

这题只有两种路径，一种是11a,一种是1a+5b，只要判断谁小就行了

题解

#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("gem.in","r",stdin);
freopen("gem.out","w",stdout);
long long a,b,ans=0;
cin>>a>>b;
if(b>2*a)
{
ans=ans+11*a;
}
else
{
ans=ans+a+5*b;
}
cout<<ans;	
return 0;
}
分类：暴力思维题

小田的好数组

思路

只要按升序数组所选的子序列一定也是升序的 输出0 否则排序后一定和原来不完全一样 输出n; (有个特判 n==1 输出0）

题解

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int main()
{
freopen("hsz.in","r",stdin);
freopen("hsz.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
if(n==1)
{
cout<<0;
return 0;
}
for(int i=1;i<=n;i++)
{
if(a[i]<a[i-1])
{
cout<<n;
return 0;
}
}
cout<<0;
}
分类：暴力思维题

没想到的原因：

没有多去思考只想着骗分 以后要多想，去找方法

小田的数字合并

思路

枚举一遍前缀和 再枚举一遍极值最小值，将前缀和-最小值和后缀和-最小值找一个最大值

题解

#include<bits/stdc++.h>
using namespace std;
long long a[200010],s[200010];
int main()
{
freopen("num.in","r",stdin);
freopen("num.out","w",stdout);
int n;
long long ans=-1;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
if(n==1)
{
cout<<0;
return 0;
}
if(n==2)
{
cout<<abs(a[1]-a[2]);
return 0;
}
for(int i=1;i<=n;i++)
{
ans=max(ans,abs(s[i-1]-a[i]));
}
for(int i=n;i>1;i--)
{
ans=max(ans,abs(s[n]-s[i-1]-a[i-1]));
}
cout<<ans;
}

分类 暴力思维题

没想到的原因：

只关注最大值和最小值，想不到优化

小W挖宝藏

思路 用记忆化搜索，将每个点都做为起点dfs ,在每次都更新一下最大值ans和坐标

题解

#include<bits/stdc++.h>
using namespace std;
int a[110][110],st[110][110];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int n,m,ans,ansx,ansy;
int DFS(int i,int j)
{
if(st[i][j]>0) return st[i][j];

for(int k=0;k<4;k++)
{
int _x=i+dx[k],_y=j+dy[k];
if(_x>0&&_x<=n&&_y>0&&_y<=m&&a[i][j]>a[_x][_y])
{
st[i][j]=max(st[i][j],DFS(_x,_y)+1);
}
else continue;
}
return st[i][j];

}
int main()
{
freopen("treasure.in","r",stdin);
freopen("treasure.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(DFS(i,j)+1>ans)
{
ans=DFS(i,j)+1;
ansx=i;
ansy=j;
}
}
}
cout<<ansx<<" "<<ansy<<endl<<ans;
}

分类 记忆化搜索（dfs)

写错的原因

没想到要用记忆化搜索，搜索没写对。

小z的等待时间

思路

如果这朵花比他前面的花更高 他的时间就是他的高度 否则就是他前面的时间+1

题解

#include<bits/stdc++.h>
using namespace std;
int a[100010],f[100010];
int main()
{
	freopen("flowers.in","r",stdin);
	freopen("flowers.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		f[i]=a[i];
	}
	for(int i=n-1;i>=1;i--)
	{
		if(f[i]<=f[i+1]) f[i]=f[i+1]+1;
	}
	cout<<f[1];
	return 0;
}

分类 简单dp

没写出来的原因

没画dp图 下次要画

总结 代码细节都注意了 ，不过没有多去思考前面几题， 只想着骗分