第一个样例是对的,最低应该也是10pts,为什么爆0了?求教!!
查看原帖
第一个样例是对的,最低应该也是10pts,为什么爆0了?求教!!
1010349
huanyizhiyuan楼主2024/4/28 20:24

为什么这个代码会爆0,是有啥问题么?我看了半天没找到呀??求教。


#include<bits/stdc++.h>
#define i64 long long
#define maxn 100050
#define pb push_back
//#define int ll
//using namespace std;
typedef std::pair<int,int> PII;
const i64 inf=1e16+5;
const i64 N=3e5+10;
const i64 mod=1e9+7;
i64 T=1,n,m,k,_a,_b,ans,cnt,sum,num,res,avg,x,y,z,zz,p,flag=1;
i64 a[10005],sum1[10005],dp[10005];

void solve()
{
	std::cin>>n>>m;
	sum1[0]=m*2;
	//我选择增加一个前缀和。
	for(int i=1;i<=n;i++)
	{
		dp[i]=inf;//要求最小值的话,每一个dp[i]都要赋值为无限大。
		std::cin>>a[i];
		sum1[i]=sum1[i-1]+a[i];
	}
	//没有容量的背包是最难的。
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dp[j]=std::min(dp[j],dp[j-i]+sum1[i]);
		//与背包类似的方程。
	std::cout<<dp[n]-m<<"\n";
}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	// std::cin>>T;
	while(T--)
	{
		solve();
	}
	return  0;
}

2024/4/28 20:24
加载中...