39 条题解
-
2faojie LV 8 @ 2017-10-18 19:21:49
这不是贪心吗?
给个例子
x为一串正整数数组
那么很显然 -x[1]-x[2]±x[3]±x[4]±...±x[n]的最大值就是-x[1]+x[2]+x[3]+...+x[n]
因为第2个负号后面的数字总可以和第一个负号或者第一个符号+离自己最近的负号(不为第一个负号)的到正值当然,第1个负号与第2个负号之间的正数会被取成负值,所以需要枚举一遍,取最大值
#include<cstdio> using namespace std; int n,tot,ans; int a[15],sum[15],fsum[15],q[15]; int readln() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while ('0'<=ch&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f; } int max(int x,int y) {return x>y?x:y;} int main() { n=readln(); for (int i=1;i<=n;i++) { a[i]=readln(); fsum[i]=fsum[i-1]; if (a[i]<0) { sum[i]=sum[i-1]-a[i]; fsum[i]+=a[i]; q[++tot]=i; } else sum[i]=sum[i-1]+a[i]; } ans=sum[n]+2*fsum[n]; for (int i=tot;i>1;i--) ans=max(ans,sum[n]-2*(sum[q[i]-1]-sum[q[i-1]-1]-fsum[q[i-1]-1])); printf("%d",ans); return 0; }
-
02017-05-15 11:43:54@
xjb区间dp没什么可以解释的,dp方程有贪心的思想
int Ma[101][101],Mi[101][101],n,a[101]; int main() { scanf("%d",&n); For(i,1,n) For(j,1,n) Mi[i][j]=1e9,Ma[i][j]=-1e9; For(i,1,n) scanf("%d",&a[i]),Ma[i][i]=Mi[i][i]=abs(a[i]); Dow(i,1,n) For(j,i+1,n) { For(k,i+1,j) { if(a[k]>=0) Ma[i][j]=max(Ma[i][j],Ma[i][k-1]+Ma[k][j]), Mi[i][j]=min(Mi[i][j],Mi[i][k-1]+Mi[k][j]); else Ma[i][j]=max(Ma[i][j],Ma[i][k-1]-Mi[k][j]), Mi[i][j]=min(Mi[i][j],Mi[i][k-1]-Ma[k][j]); } } printf("%d",Ma[1][n]); }
-
02015-01-29 12:32:18@
分治(或者叫DP?没有用记忆化也差不多掉了)
求出数组中区间0..n-1所能得到的最小值与最大值.
求出所有子区间的最大最小值,推出当前处理区间的最大最小值.###Block code
int n;
int a[200];pl DC(int l,int r)
{
if(l==r) return pl(abs(a[l]),abs(a[l]));
pl v(-INF,INF);
for(int i=l;i<r;i++)
{
if(a[i+1]<0)
{
v.first=max(v.first, DC(l,i).first-DC(i+1,r).second );
v.second=min(v.second, DC(l,i).second-DC(i+1,r).first );}else
{
v.first=max(v.first, DC(l,i).first+DC(i+1,r).first );
v.second=min(v.second, DC(l,i).second+DC(i+1,r).second );
}
}
return v;
}int main()
{
ios::sync_with_stdio(false);cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];cout<<DC(0,n-1).first<<endl;
return 0;
} -
02009-11-11 18:02:54@
搜索秒杀。。。
-
02009-11-02 00:01:53@
啊~~~~~~~~~~DP~~~~~~~~~~~
---|---|---|---|---|---|---|---|---|---|-
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0msp数组记录符号,a记录绝对值,
f若k=1表示i,j段能构成的最大值,若k=-1表示i,j断的最小值!
f:=max(find(i,h,k)+p[h+1]*find(h+1,j,k*p[h+1]),f);
f:=min(find(i,h,k)+p[h+1]*find(h+1,j,k*p[h+1]),f); -
02009-11-01 14:05:07@
#include
using namespace std;
int main(void)
{
int i,j,t,k,n,a[101],f[101][101][2],b[101];
cin>>n;
for (i=1;i>a[i];
if (a[i]>=0)
b[i]=0;
else
{
b[i]=1;
a[i]=-a[i];
}
f[i][i][0]=f[i][i][1]=a[i];
}
for (t=1;t -
02009-10-19 12:39:59@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms -
02009-05-14 19:42:25@
什么破题目。。。讲就讲清楚。。。
注意。如果第一个是负数。那么相当于第一个数为0(即也能加括号)。
我的算法是O(N^4).
max[i][j]表示区间的最大值。min[i][j]表示区间的最小值。
对于区间[h,t]。f[i],g[i]分别表示前i个数的最大/小值。
对运算符进行讨论即可。
所求为max[1][n]; -
02009-04-01 16:04:28@
f第i个位置前有j个左括号和k个右括号时的最大值
(-1)^(j-k)*a[i]是该加上的值,注意初始化只有负数前才可加左括号 -
02009-03-28 12:37:24@
Z-Force.Cho
你的程序是错误的
输入
2
-4
5
你会输出-9
动规的话我觉得需要存一个最大和最小值
for i:=1 to n do
begin
read(a[i]);
f1:=a[i]; f2:=a[i];
end;
for l:=2 to n do
for i:=1 to n-l+1 do
begin
j:=i+l-1;
f1:=a[i]+f1;
f2:=a[i]+f2;
//如果a[i]>=0则不需要枚举了,因为在第一个数上加括号毫无意义
if a[i] -
02008-10-29 13:09:05@
这道题的DP方法之所以难想到,很大原因是因为我们不习惯对正负号的操作。数据很弱,搜索完全可以做到0MS。
过程 DFS(T,KUO,HE);
T表示将要操作的第T个数,KUO表示在T之前已经加了的左括号数,HE表示前T-1个数之和
N个树存储在A数组里
当A[T]>=0时,再加一个左括号与不加左括号对后面的数据无影响..
而当A[T]0时,需要搜索加一个右括号的情况.代码如下:
if a[t]>=0 then
begin
if kuo>0 then
begin
if kuo mod 2=1 then x:=he+a[t] else x:=he-a[t];
dfs(t+1,kuo-1,x);
end;
if kuo mod 2=0 then x:=he+a[t] else x:=he-a[t];
dfs(t+1,kuo,x);
end
else
begin
if kuo>0 then
begin
if (kuo-1) mod 2=0 then x:=he+a[t] else x:=he-a[t];
dfs(t+1,kuo-1,x);
dfs(t+1,kuo,x);
end;
if kuo mod 2=0 then x:=he+a[t] else x:=he-a[t];
dfs(t+1,kuo,x);
dfs(t+1,kuo+1,x);
end; -
02008-10-23 19:26:00@
DP...想了很长时间。。。
-
02008-10-04 15:39:46@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0msdp,不简单额,秒杀
-
02008-09-25 19:08:09@
其实搜索就可以了^^
-
02008-09-13 15:11:21@
var
n:longint;
a:array[1..10] of longint;
b:array[1..10,1..10] of longint;Procedure Dp;
var
i,j,k,x:longint;
begin
for i:=n-1 downto 1 do
begin
if a[i] -
02008-08-13 17:26:51@
O(n^2)?
经典O(n^3).... -
02007-11-12 10:47:53@
O(n^2)
-
02007-11-10 22:32:03@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms -
02007-10-27 19:12:12@
数据中有0..
而且必须看成+0
...
我晕倒 -
02007-10-04 17:41:00@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms晕~花了我一下午的时间