陈柏衡
(陈柏衡)
1
#include<bits/stdc++.h>
using namespace std;
int n,ans=0x3f3f3f3f;
int dp_0[300005][2],dp_1[300005][2],a[300005];
int main()
{
memset(dp_0,63,sizeof(dp_0));
dp_0[2][1]=a[2];
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=3;i<=n;i++)
{
dp_0[i][1]=min(dp_0[i-1][1],dp_0[i-1][0])+a[i];
dp_0[i][0]=dp_0[i-1][1];
}
ans=dp_0[n][1];
dp_1[1][1]=a[1];
for(int i=2;i<=n;i++)
{
dp_1[i][1]=min(dp_1[i-1][1],dp_1[i-1][0])+a[i];
dp_1[i][0]=dp_1[i-1][1];
}
ans=min(min(dp_1[n][0],dp_1[n][1]),ans);
cout<<ans;
return 0;
}
C. 小信喂狗狗
Problem ID: 8576
Contest ID: 5883
必做题
Wrong Answer
8 分
时间：2s 空间：256M
题目描述：
小信家里有
�
n只狗狗围成了一圈要吃零食，第
�
i和第
�
+
1
i+1只狗狗吃到价格为
�
�
a
i
的零食就会开心，特别的，第
�
n和第
1
1只狗狗吃到价格为
�
�
a
n
的零食会开心，请问让所有狗狗开心的最少花费。
输入格式：
第一行包含一个整数
�
n。
第二行包含
�
n 个整数
�
�
a
i
。
输出格式：
输出一个整数表示答案。
样例1输入：
5
2 5 3 2 5
样例1输出：
7
约定与提示：
对于100%的数据，
2
≤
�
≤
3
⋅
1
0
5
2≤n≤3⋅10
5
，
1
≤
�
�
≤
1
0
9
1≤a
i
≤10
9
。
样例1解释：购买第1，3，4种零食能让所有狗狗开心，花费是
2
+
3
+
2
=
7
2+3+2=7。
2 个赞
陈柏衡
(陈柏衡)
2
#include<bits/stdc++.h>
using namespace std;
int n,ans=0x3f3f3f3f;
int dp_0[300005][2],dp_1[300005][2],a[300005];
int main()
{
memset(dp_0,0x3f3f3f3f,sizeof(dp_0));
memset(dp_1,0x3f3f3f3f,sizeof(dp_1));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
dp_0[2][1]=a[2];
for(int i=3;i<=n;i++)
{
dp_0[i][1]=min(dp_0[i-1][1],dp_0[i-1][0])+a[i];
dp_0[i][0]=dp_0[i-1][1];
}
ans=dp_0[n][1];
dp_1[1][1]=a[1];
for(int i=2;i<=n;i++)
{
dp_1[i][1]=min(dp_1[i-1][1],dp_1[i-1][0])+a[i];
dp_1[i][0]=dp_1[i-1][1];
}
ans=min(min(dp_1[n][0],dp_1[n][1]),ans);
cout<<ans;
return 0;
}
WA24
2 个赞
