首页 > 代码库 > hdu 4223 Dynamic Programming?

hdu 4223 Dynamic Programming?

2024-08-15 17:42:30   245人阅读

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?
 

 

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.

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
221 -141 2 1 -2
 

 

Sample Output
Case 1: 0Case 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-14const int N=2e5+10,M=4e6+10,inf=1e9+10,mod=1e9+7;const ll INF=1e18+10;int a[N];int pre[N];int main(){    int T,cas=1;    scanf("%d",&T);    while(T--)    {        int n;        scanf("%d",&n);        for(int i=1;i<=n;i++)           scanf("%d",&a[i]);        for(int i=1;i<=n;i++)            pre[i]=pre[i-1]+a[i];        int ans=inf;        for(int i=1;i<=n;i++)            for(int t=i;t<=n;t++)            {                ans=min(ans,abs(pre[t]-pre[i-1]));            }        printf("Case %d: %d\n",cas++,ans);    }    return 0;}

 

 

hdu 4223 Dynamic Programming?


联系
我们