dp 题写贪心还想过 ¿
by WYXkk @ 2020-11-17 15:11:59
~~先不提你1e5次2e3的solve~~
你solve的贪心不对
by Binah @ 2020-11-17 15:25:37
@[Binah](/user/101407) 我用了绝对正确的check函数，还是二分不到答案。 答案是20多 这二分给我跑到 218 220 左右就在这死循环了。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=2501;
int a[maxn];
int m,n;
int be[2505],sum[2505],dp[2505];
bool solve(int cishu){
int num1=0;
int num2=0;
int tim=0;
for(int i=0;i<m;i++){
if(a[i]==1)num1++;
else num2++;
if(num1&&num2&&abs(num1-num2)>n){
if(a[i]==1){num1=1;num2=0;}
else {num2=1;num1=0;}
tim++;
}
}
if(num1||num2)tim++;
if(tim<=cishu)return true;
return false;
}
bool relsolve(int cishu){
memset(dp,0x7f,sizeof(dp));
for(int i=1;i<=m;i++)
{
for(int j=1;j<=i;j++)
{
if(abs(sum[i]-sum[j-1])==i-j+1||abs(sum[i]-sum[j-1])<=n)
{
dp[i]=min(dp[i],dp[j-1]+1);
}
}
}
if(dp[m]<=cishu)return true;
return false;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=0;i<m;i++){
scanf("%d",&a[i]);
}
//memset(dp,)
for(int i=1;i<=n;i++)
{
//read(be[i]);
if(a[i]==1) sum[i]=sum[i-1]+1; //前缀和
else sum[i]=sum[i-1]-1;
}
int l=1;
int r=m+`;
for(int i=0;i<1e4;i++){
int mid=l+((r-l)>>1);
if(solve(mid)){
r=mid;
//cout<<"tesst"<<mid<<endl;
}
else l=mid-1;
//cout<<"**"<<l<<"??"<<r<<" "<<mid<<endl;
}
printf("%d\n",l);
return 0;
}
```
by abcd156555 @ 2020-11-24 17:11:00