Dynamic Programming?
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
Dynamic Programming, short for DP, is the favorite of iSea. It is a method for solving complex problems by breaking them down into simpler sub-problems. It is applicable to problems exhibiting the properties of overlapping sub-problems which are only slightly smaller and optimal substructure.
Ok, here is the problem. Given an array with N integers, find a continuous subsequence whose sum’s absolute value is the smallest. Very typical DP problem, right?
Ok, here is the problem. Given an array with N integers, find a continuous subsequence whose sum’s absolute value is the smallest. Very typical DP problem, right?
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case includes an integer N. Then a line with N integers Ai follows.
Each test case includes an integer N. Then a line with N integers Ai follows.
Technical Specification
1. 1 <= T <= 100
2. 1 <= N <= 1 000
3. -100 000 <= Ai <= 100 000
Output
For each test case, output the case number first, then the smallest absolute value of sum.
Sample Input
2
2
1 -1
4
1 2 1 -2
2
1 -1
4
1 2 1 -2
Sample Output
Case 1: 0
Case 2: 1
Case 2: 1
Author
iSea@WHU
Source
思路：暴力，我以为会T，还想用treap优化一下。。。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
const int N=2e5+,M=4e6+,inf=1e9+,mod=1e9+;
const ll INF=1e18+;
int a[N];
int pre[N];
int main()
{
int T,cas=;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
pre[i]=pre[i-]+a[i];
int ans=inf;
for(int i=;i<=n;i++)
for(int t=i;t<=n;t++)
{
ans=min(ans,abs(pre[t]-pre[i-]));
}
printf("Case %d: %d\n",cas++,ans);
}
return ;
}