两个 min 函数,恐怖地错了。求大佬指点。
void gmi(int &x,int y) {x=x<y?x:y;};
gmi(f[l][c][k+1],f[i][j][k]+c2(l-i-1));
f[l][c][k+1]=min(f[l][c][k+1],f[i][j][k]+c2(l-i+1));
我觉得这两个代码没啥区别,为什么这题用上面就对,用下面就错?这是为什么?
https://www.luogu.com.cn/problem/CF1420E
原代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool tu[110];
int n,zai[110],yi,f[81][6401][81],m;
int c2(int x) {return x*(x-1)/2;}
void gmi(int &x,int y) {x=x<y?x:y;};
void readb(bool &x)
{
x=0;
char c=getchar();
while(c<'0'||c>'9') {c=getchar();}
while(c>='0'&&c<='9') {if(c=='1') x=1;c=getchar();}
}
signed main()
{
cin>>n;m=c2(n);
for(int i=1;i<=n;i++)
{
readb(tu[i]);
if(tu[i]) zai[++yi]=i;
}
if(yi==n)
{
for(int i=0;i<=m;i++) putchar('0'),putchar(' ');
return 0;
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)
{
f[i][abs(zai[1]-i)][1]=c2(i-1);
for(int j=0;j<=m;j++)
for(int k=1;k<=i&&k<yi;k++)
{
int r=yi-k;
if(f[i][j][k]!=0x3f3f3f3f)
for(int l=i+1;l<=n-r+1;l++)
{
int c=j+abs(zai[k+1]-l);
if(c<=m)
//??????????????????????????????????????????????
gmi(f[l][c][k+1],f[i][j][k]+c2(l-i-1));
// f[l][c][k+1]=min(f[l][c][k+1],f[i][j][k]+c2(l-i+1));
//??????????????????????????????????????????????
}
}
}
int res=c2(n-yi),zong=res;
for(int j=0;j<=m;j++)
{
for(int i=yi;i<=n;i++)
if(f[i][j][yi]!=0x3f3f3f3f)
res=min(res,f[i][j][yi]+c2(n-i));
printf("%lld ",zong-res);
}
return 0;
}
感觉没啥问题啊?数组也没越界。 求大神看看。