2018南昌邀请赛网络赛d题
程序员文章站
2024-03-18 23:30:04
...
刚开始看到此提时也没想到dp
但是仔细一思考可以发现确实是
我们只要单独处理第一位数
剩下的符号和数字看成一个物品
进行类似背包的dp即可
首先预处理所有火柴和符号
根据输入的总火柴进行一次dp即可
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
int cost[10]= {6,2,5,5,4,5,6,3,7,6}; //单个数字花费
int num[15][100];//大数花费
int nnum[15][100];
char s[105];
int dig[105];
int dp[105][805];
int main()
{
memset(num,0,sizeof(num));
int n;//预处理出num数组
for(int i=1; i<=9; i++) //九位数
{
for(int k=0; k<=9; k++)//10个数字哪个
{
if(i==1&&k==0) continue;
for(int j=0; j<=63; j++)
{
if(num[i-1][j]!=0||j==0)
num[i][j+cost[k]]=max(num[i-1][j]*10+k,num[i][j+cost[k]]);
}
}
}
for(int i=1; i<=9; i++) //九位数
{
for(int j=2*i; j<=7*i; j++)
{
nnum[i][j+2]=num[i][j];
//cout<<j+2<<"->"<<nnum[i][j+2]<<endl;
}
nnum[i][i*2+1]=-num[i][i*2];
}
// for(int i=1;i<=9;i++)
// {
// for(int j=2*i;j<=7*i;j++)
// {
// printf("%d->%d ",j,num[i][j]);
// }
// cout<<endl;
// }
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
scanf("%s",s+1);
int len=n;
int cnt=1;
int pos=0;
int sum=0;
for(int i=1; i<=len; i++)
{
//cout<<"q"<<endl;
if(s[i]=='+')
{
sum+=2;
dig[cnt]=pos;
cnt++;
pos=0;
}
if(s[i]=='-')
{
//sum+=pos;
sum+=1;
dig[cnt]=pos;
cnt++;
pos=0;
}
if(s[i]=='1') sum+=2,pos++;
if(s[i]=='2') sum+=5,pos++;
if(s[i]=='3') sum+=5,pos++;
if(s[i]=='4') sum+=4,pos++;
if(s[i]=='5') sum+=5,pos++;
if(s[i]=='6') sum+=6,pos++;
if(s[i]=='7') sum+=3,pos++;
if(s[i]=='8') sum+=7,pos++;
if(s[i]=='9') sum+=6,pos++;
if(s[i]=='0') sum+=6,pos++;
//cout<<i<<"->"<<sum<<endl;
}
//sum+=pos;
dig[cnt]=pos;
for(int i=0; i<=100; i++)
{
for(int j=0; j<=800; j++)
{
dp[i][j]=-1000000000;
}
}
dp[0][0]=0;
if(cnt==1)
{
printf("%d\n",num[pos][sum]);
}
else
{
for(int i=1; i<=cnt; i++) //多少位
{
//cout<<i<<"->"<<dig[i]<<endl;
if(i!=1)
{
for(int j=2*dig[i]+1; j<=7*dig[i]+2; j++) //
{
for(int k=0; k<=sum; k++)
{
//if(dp[i-1][j]>=-1e8)
dp[i][k+j]=max(dp[i-1][k]+nnum[dig[i]][j],dp[i][k+j]);
}
}
}
else
{
for(int j=2*dig[i]; j<=7*dig[i]; j++) //
{
for(int k=0; k<=sum; k++)
{
if(k==0&&k+j<sum)
{
dp[i][k+j]=max(dp[i-1][k]+num[dig[i]][j],dp[i][k+j]);
//cout<<j<<num[dig[i]][j]<<endl;
//cout<<k+j<<" "<<dp[i][k+j]<<endl;
}
}
}
}
}
cout<<dp[cnt][sum]<<endl;
}
}
}