UVa10684
題敘
想法1
直觀的看，暴力去找起點跟終點 $i,j$
複雜度$O(N^2)$
Code1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int n,arr[10000];
int main(){
IOS
while(cin>>n && n){
cin>>arr[1];
for(int i=2,tmp ; i<=n ; i++){
cin>>tmp;
arr[i]=arr[i-1]+tmp;
}
int ans=-2147483647;
for(int i=1 ; i<=n ; i++){
for(int j=i ; j<=n ; j++){
ans=max(ans, (arr[j]-arr[i-1]));
}
}
if(ans>0)
cout<<"The maximum winning streak is "<<ans<<".\n";
else
cout<<"Losing streak.\n";
}
return 0;
}
|
雖然說UVa上能過，但是超過1s實在太慢
想法二
對於每個點來說都只有 取 跟 不取 兩種狀態，針對兩種狀態可以寫出DP式
定義$DP[i][j]$表示當第$i$個為取或不取時的最大值，$j=0$表不取，$j=1$表取
則可得
- $DP[i][0] = 0$
- $DP[i][1] = max(DP[i-1][1]+arr[i], DP[i-1][0]+arr[i])$
因為必須保證取的段是連續的，所以當不取時就會是0
Code2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int n,arr[10005],dp[10005][2];
int main(){
IOS
while(cin>>n && n){
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
int ans=-2147483647;
dp[0][0]=0;
dp[0][1]=arr[0];
ans=max(ans,dp[0][1]);
for(int i=1 ; i<n ; i++){
dp[i][0]=0;
dp[i][1]=max(dp[i-1][1]+arr[i], dp[i-1][0]+arr[i]);
ans=max(ans,dp[i][1]);
}
if(ans<=0)
cout<<"Losing streak.\n";
else
cout<<"The maximum winning streak is "<<ans<<".\n";
}
return 0;
}
|
想法3
針對想法2可以再做改良
可以發現到其實無論如何$DP[i][0] = 0$恆成立，所以其實沒必要存在
因此DP式化簡為 $DP[i]=max(DP[i-1]+arr[i],arr[i])$
Code3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int n,arr[10005],dp[10005];
int main(){
IOS
while(cin>>n && n){
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
int ans=max(-2147483647,arr[0]);
for(int i=0 ; i<n ; i++){
dp[i]=max(dp[i-1]+arr[i],arr[i]);
ans=max(ans,dp[i]);
}
if(ans<=0)
cout<<"Losing streak.\n";
else
cout<<"The maximum winning streak is "<<ans<<".\n";
}
return 0;
}
|
複雜度
每次狀態轉移複雜度為 $O(1)$
而須轉移$n$次，總複雜度 $O(n)$