Seauy @ 2020-09-12 11:53:07
dp 最大值 1e14 -> 1061109567 就过了，之前开了 long long 的
是不是出数据的人忘了开 long long 啊
极限数据应该就能把最大值开小的给卡了？
by Seauy @ 2020-09-12 11:57:38
被题解给坑了，跟他们对拍了两天，结果他们全是 memset(dp,-0x3f3f3f3f,sizeof dp) 以为是我写错了
极值改大些又跟我答案一样了
by Seauy @ 2020-09-12 12:12:41
提供我的写法：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e3;
struct msg
{
ll x,y,v;
void Print() {printf("%lld %lld %lld\n",x,y,v);}
}Ball[MAXN+5];
int n;ll ans;
ll x0,dp[2][MAXN+5][MAXN+5],pre[2][MAXN+5];
bool visit[2][MAXN+5][MAXN+5];
bool cmp(msg a,msg b)
{return a.x<b.x;}
ll DFS(bool t,int L,int R)
{
if(visit[t][L][R]) return dp[t][L][R];
visit[t][L][R]=1;
if(x0<Ball[L].x || Ball[R].x<x0 || L>R) return dp[t][L][R]=100000000000;
if(L==R && Ball[L].x==x0 && !Ball[L].v && !Ball[L].y) return dp[t][L][R]=0;
dp[t][L][R]=100000000000;
if(t)//在右端
{
dp[1][L][R]=min(dp[1][L][R],(Ball[R].x-Ball[L ].x)*(pre[0][L-1]+pre[1][R])+DFS(0,L,R-1));//去左边
dp[1][L][R]=min(dp[1][L][R],(Ball[R].x-Ball[R-1].x)*(pre[0][L-1]+pre[1][R])+DFS(1,L,R-1));//去右边
}
else//在左端
{
dp[0][L][R]=min(dp[0][L][R],(Ball[L+1].x-Ball[L].x)*(pre[0][L]+pre[1][R+1])+DFS(0,L+1,R));
dp[0][L][R]=min(dp[0][L][R],(Ball[R ].x-Ball[L].x)*(pre[0][L]+pre[1][R+1])+DFS(1,L+1,R));
}
return dp[t][L][R];
}
int main()
{
//freopen("test.txt","r",stdin);
//freopen("MyAns.txt","w",stdout);
scanf("%d %lld",&n,&x0);
for(int i=1;i<=n;i++) scanf("%lld",&Ball[i].x);
for(int i=1;i<=n;i++)
{
scanf("%lld",&Ball[i].y);
ans+=Ball[i].y;
}
for(int i=1;i<=n;i++) scanf("%lld",&Ball[i].v);
Ball[++n].x=x0;
sort(Ball+1,Ball+n+1,cmp);
//for(int i=1;i<=n;i++) Ball[i].Print();
for(int i=1;i<=n;i++) pre[0][i]=pre[0][i-1]+Ball[i].v;
for(int i=n;i>=1;i--) pre[1][i]=pre[1][i+1]+Ball[i].v;
/*
for(int i=1;i<=n;i++)
if(Ball[i].x==x0 && !Ball[i].y && !Ball[i].v) printf("start at %d\n",i);
*/
printf("%.3lf\n",(ans-min(DFS(0,1,n),DFS(1,1,n)))/1000.0);
/*
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
printf("L: %d R: %d dp: %lld %lld\n",i,j,dp[0][i][j],dp[1][i][j]);
//cout<<visit[0][i][j]<<' '<<visit[1][i][j]<<endl;
//printf("%lld %lld\n",Ball[i].x,Ball[j].x);
}
*/
return 0;
}
/*
4 0
-4 -2 2
22 30 26
1 9 8
-4 3 5
20 -446
-7606 -8514 -8251 -5358 2403 -9449 -6383 -5014 6881 8809 -9832 1538 6827 8080 5109 2685 1739 -7718 -7577 -6071
1894 -3822 8712 -4187 -6423 -5574 -958 -1878 2468 -5135 7169 1188 -7012 -6274 -6876 -226 2010 3085 -328 5898
2360 2915 5509 6918 3504 1913 5034 2268 3949 4328 5942 2829 7876 2706 652 4381 9703 6372 7071 652
*/by yummy @ 2020-09-12 12:28:31
请不要怀疑一个612AC的题目
by Seauy @ 2020-09-12 12:30:47
@yummy 然鹅随便拉一个题解下来，极限数据挂了
by Alarm5854 @ 2020-09-12 13:27:02
@QuantumCheshireCat 极限数据给我运行一下
by Seauy @ 2020-09-12 13:38:13
@YCE3216037 生成方案与答案
比如第一篇题解，运行结果 -1061109.567 正是 -0x3f3f3f3f
by Seauy @ 2020-09-12 13:40:01
啊，用 for 循环赋值他的答案是 -0x3f3f3f3f
但是用 memset 是 -595821.444 依旧错误
by Seauy @ 2020-09-12 13:45:58
之前我的代码初值还是赋小了……
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e3;
struct msg
{
ll x,y,v;
void Print() {printf("%lld %lld %lld\n",x,y,v);}
}Ball[MAXN+5];
int n;ll ans;
ll x0,dp[2][MAXN+5][MAXN+5],pre[2][MAXN+5];
bool visit[2][MAXN+5][MAXN+5];
bool cmp(msg a,msg b)
{return a.x<b.x;}
ll DFS(bool t,int L,int R)
{
if(visit[t][L][R]) return dp[t][L][R];
visit[t][L][R]=1;
if(x0<Ball[L].x || Ball[R].x<x0 || L>R) return dp[t][L][R]=10000000000000;
if(L==R && Ball[L].x==x0 && !Ball[L].v && !Ball[L].y) return dp[t][L][R]=0;
dp[t][L][R]=10000000000000;
if(t)//在右端
{
dp[1][L][R]=min(dp[1][L][R],(Ball[R].x-Ball[L ].x)*(pre[0][L-1]+pre[1][R])+DFS(0,L,R-1));//去左边
dp[1][L][R]=min(dp[1][L][R],(Ball[R].x-Ball[R-1].x)*(pre[0][L-1]+pre[1][R])+DFS(1,L,R-1));//去右边
}
else//在左端
{
dp[0][L][R]=min(dp[0][L][R],(Ball[L+1].x-Ball[L].x)*(pre[0][L]+pre[1][R+1])+DFS(0,L+1,R));
dp[0][L][R]=min(dp[0][L][R],(Ball[R ].x-Ball[L].x)*(pre[0][L]+pre[1][R+1])+DFS(1,L+1,R));
}
return dp[t][L][R];
}
int main()
{
//freopen("Largest.txt","r",stdin);
//freopen("MyAns.txt","w",stdout);
scanf("%d %lld",&n,&x0);
for(int i=1;i<=n;i++) scanf("%lld",&Ball[i].x);
for(int i=1;i<=n;i++)
{
scanf("%lld",&Ball[i].y);
ans+=Ball[i].y;
}
for(int i=1;i<=n;i++) scanf("%lld",&Ball[i].v);
Ball[++n].x=x0;
sort(Ball+1,Ball+n+1,cmp);
//for(int i=1;i<=n;i++) Ball[i].Print();
for(int i=1;i<=n;i++) pre[0][i]=pre[0][i-1]+Ball[i].v;
for(int i=n;i>=1;i--) pre[1][i]=pre[1][i+1]+Ball[i].v;
/*
for(int i=1;i<=n;i++)
if(Ball[i].x==x0 && !Ball[i].y && !Ball[i].v) printf("start at %d\n",i);
*/
printf("%.3lf\n",(ans-min(DFS(0,1,n),DFS(1,1,n)))/1000.0);
/*
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
printf("L: %d R: %d dp: %lld %lld\n",i,j,dp[0][i][j],dp[1][i][j]);
//cout<<visit[0][i][j]<<' '<<visit[1][i][j]<<endl;
//printf("%lld %lld\n",Ball[i].x,Ball[j].x);
}
*/
return 0;
}
/*
4 0
-4 -2 2
22 30 26
1 9 8
-4 3 5
20 -446
-7606 -8514 -8251 -5358 2403 -9449 -6383 -5014 6881 8809 -9832 1538 6827 8080 5109 2685 1739 -7718 -7577 -6071
1894 -3822 8712 -4187 -6423 -5574 -958 -1878 2468 -5135 7169 1188 -7012 -6274 -6876 -226 2010 3085 -328 5898
2360 2915 5509 6918 3504 1913 5034 2268 3949 4328 5942 2829 7876 2706 652 4381 9703 6372 7071 652
*/by Alarm5854 @ 2020-09-12 13:51:03
@QuantumCheshireCat 我的没有被hACk
by Seauy @ 2020-09-12 14:12:35
@YCE3216037 那你去发一篇题解吧……？