90pts WA#7 内有思路求调

思路

数组定义

dp_{i,k}

表示使用

i

个加号以及前

j

（即字符串s的前

j

）个数字所能组成的与

n

差值最小的数

显而易见

0≤i<len_s

;

i≤j<len_s

;

转移方程

0____ i_k______j

_______	_______	_______

对于

dp_i._j

我们可以发现他的取值来源于本身或通过少使用一个加号的前状态转移，我们可以枚举最后一个加号（第

i

个加号）的位置

k

将

1-j

分为

1-k

和

k+1-j

两段，其中前一段用了

i-1

个加号而后一段没有使用故得到转移方程：

if(|n-dp_{i,j}|>|n-dp_{i-1,k}-num_{(k+1)⇨j}|) dp_{i,j}=dp_{i-1,k}+num_{(k+1)⇨j}

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int MAXN=42;
string s;
int n;
long long dp[MAXN][MAXN];
int main(){
	memset(dp,0x3f,sizeof(dp));
	cin>>s;
	scanf("%d",&n);
	int N=s.size();
	dp[0][0]=0;
	for(int i=1;i<=N;i++){
		dp[0][i]=min(dp[0][i-1]*10+(s[i-1]-'0'),dp[0][i]);
	}
	for(int i=1;i<N;i++)
	    for(int j=i;j<=N;j++)
	        for(int k=j-1;k>=i;k--){
	        	int cnt=0;
	        	for(int x=k+1;x<=j;x++){
	        		cnt=cnt*10+(s[x-1]-'0');
	        		if(cnt>1e5+2) break;
				}
	        	if(abs(n-dp[i][j])>abs(n-dp[i-1][k]-cnt)) dp[i][j]=dp[i-1][k]+cnt;
			}
	for(int i=0;i<N;i++)
		if(dp[i][N]==n){
			printf("%d",i);
			return 0;
		}
	printf("-1");
	return 0;
}

90pts WA#7 内有思路求调

讨论操作

思路

数组定义

转移方程

0____ i_k______j

代码

回复

相关推荐

90pts WA#7 内有思路求调

讨论操作

思路

数组定义

转移方程

0__________ i___________k__________j

代码

回复

相关推荐

0____ i_k______j