C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 1120K, 提交时间: 2019-01-11 17:22:42

#include<bits/stdc++.h>
using namespace std;
int n,t,ans;
char s[405];
int dp[405][405];
int main(){
	scanf("%d%d",&n,&t);
	getchar();
	scanf("%s",s+1);
	for(int i=0;i<=n;i++)
		dp[0][i]=1e8;
	dp[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j]=dp[i-1][j];
			if(s[i]!='0'&&j<=i){
				for(int k=1;k<=j&&s[i-k+1]!='0';k++)
					dp[i][j]=min(dp[max(0,i-k-1)][j-k]+k*(k+1)/2,dp[i][j]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(dp[n][i]<=t)
		ans=i;
	printf("%d\n",ans);
}

C++(g++ 7.5.0) 解法, 执行用时: 30ms, 内存消耗: 1116K, 提交时间: 2023-04-27 15:33:17

#include<iostream>
#include<string.h>
using namespace std;
int f[401][401];
int main()
{
	int n,K;
	string str;
	cin>>n>>K;
	cin>>str;
	memset(f,0x3f3f3f3f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j>=1;j--)
		{
			for(int k=j;k>=1;k--)
			{
				f[j][0]=min(f[j][0],f[j][k]);
				if(str[i-1]=='1')
				f[j][k]=min(f[j][k],f[j-1][k-1]+k);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(f[i][j]<=K)
			ans=i;
		}
	}
	cout<<ans<<endl;
 } 

C++(clang++11) 解法, 执行用时: 29ms, 内存消耗: 1116K, 提交时间: 2020-12-09 18:20:24

#include<bits/stdc++.h>
using namespace std;
const int nx=4e2+5;
int f[nx][nx],n,k;
char s[nx];
int main(){
	scanf("%d%d%s",&n,&k,s+1);
	memset(f,0x3f,sizeof f);
	f[0][0]=0;
	for(int i=1;i<=n;++i)
		for(int j=i;j;--j)
			for(int w=1;w<=j;++w){
				f[j][0]=min(f[j][0],f[j][w]);
				if(s[i]=='1')f[j][w]=min(f[j][w],f[j-1][w-1]+w);
			}
	for(int i=n;~i;--i)
		for(int j=0;j<=i;++j)
			if(f[i][j]<=k){
				printf("%d",i);
				return 0;
			}
}