WA#5,90,玄关(让我改对才关)
查看原帖
WA#5,90,玄关(让我改对才关)
1023960
135791a楼主2024/8/3 15:00
#include<bits/stdc++.h>
using namespace std;
long long n,a[1005],sum[1005],dp[1005];
int main(){
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	if (sum[n]<0) {
		cout<<"Impossible";
		return 0;
	}
	for (int i=1;i<=n;i++) {
		dp[i]=0;
		for (int j=0;j<i;j++) {
			if (sum[i]-sum[j]>=0) {
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
	}
	cout<<dp[n];
	return 0;
} 
#5.in
50
1202
706
-1275
-1337
1847
1426
510
1160
-2186
-2417
2227
1160
1382
-189
2075
-932
-1291
-1617
-1326
391
-1594
1120
1214
-782
75
1887
2289
677
1688
119
-1977
-1676
-304
-1276
2080
-1923
1636
1946
-1744
1065
-1048
-1316
1365
1746
-448
-905
321
1252
-1396
-1106

#5.out
8
me.out
9
2024/8/3 15:00
加载中...