题目大意：一个长度为n的序列a，可以在每两个元素间添加加号或乘号，一共可以添加k个乘号，n-k-1个加号，括号可以随便加，请你求出最大的结果，n≤15。
明显的区间DP啊，设f[i][j][p]为[i,j]区间中有p个乘号的最大值。
f[i][j][p]=max{f[i][t][q]+f[t+1][j][p-q],f[i][t][q]×f[t+1][j][p-q-1]}
时间复杂度达到了优秀的O(n5)，但还是稳稳过的。
兴冲冲地交上去，只得了63pts，被有0的数据hack了。
程序交给各位大神debug：
#include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<map> using namespace std; #define int long long #define INF 0x3f3f3f3f inline int read() { char ch; bool bj=0; while(!isdigit(ch=getchar())) bj|=(ch=='-'); int res=ch^(3<<4); while(isdigit(ch=getchar())) res=(res<<1)+(res<<3)+(ch^(3<<4)); return bj?-res:res; } void printnum(int x) { if(x>9)printnum(x/10); putchar(x%10+'0'); } inline void print(int x,char ch) { if(x<0) { putchar('-'); x=-x; } printnum(x); putchar(ch); } int n,k,a[20]; int f[20][20][20]; signed main() { n=read(); k=read(); for(int i=1; i<=n; i++) { a[i]=read(); f[i][i][0]=a[i]; } for(int len=2; len<=n; len++) for(int i=1; i<=n-len+1; i++) { int j=i+len-1; for(int p=0; p<=j-i; p++) for(int l=i; l<j; l++) for(int q=0; q<=p; q++) { if(p-q-1>=0)f[i][j][p]=max(f[i][j][p],f[i][l][q]*f[l+1][j][p-q-1]); f[i][j][p]=max(f[i][l][q]+f[l+1][j][p-q],f[i][j][p]); } } print(f[1][n][k],' '); return 0; }
不想改，怎么办，考虑到n的范围这么小，何苦不把所有的符号情况枚举出来再区间DP呢？
状态定义类似上面，笔者偷懒不再写。
#include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<map> using namespace std; #define int long long #define INF 0x3f3f3f3f inline int read() { char ch; bool bj=0; while(!isdigit(ch=getchar())) bj|=(ch=='-'); int res=ch^(3<<4); while(isdigit(ch=getchar())) res=(res<<1)+(res<<3)+(ch^(3<<4)); return bj?-res:res; } void printnum(int x) { if(x>9)printnum(x/10); putchar(x%10+'0'); } inline void print(int x,char ch) { if(x<0) { putchar('-'); x=-x; } printnum(x); putchar(ch); } int n,k,a[20]; int f[20][20]; char s[20];//s[i]介于a[i]和a[i+1]之间 int ans=-INF; inline int cal(int x,int y,char ch) { return ch=='+'?x+y:x*y; } inline int DP() { memset(f,0,sizeof(f)); for(int i=1; i<=n; i++)f[i][i]=a[i]; for(int len=2; len<=n; len++) for(int i=1; i<=n-len+1; i++) { int j=i+len-1; for(int l=i; l<j; l++)f[i][j]=max(f[i][j],cal(f[i][l],f[l+1][j],s[l])); } return f[1][n]; } void DFS(int pos,int num1,int num2) { if(pos==n) { ans=max(ans,DP()); return; } if(num1<k) { s[pos]='*'; DFS(pos+1,num1+1,num2); } if(num2<n-k-1){ s[pos]='+'; DFS(pos+1,num1,num2+1); } } signed main() { n=read(); k=read(); for(int i=1; i<=n; i++)a[i]=read(); DFS(1,0,0); print(ans,' '); return 0; }
然鹅并不能AC，因为洛谷数据好像咕了，真正的AC代码是这样的！
#include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<map> using namespace std; #define int long long #define INF 0x3f3f3f3f inline int read() { char ch; bool bj=0; while(!isdigit(ch=getchar())) bj|=(ch=='-'); int res=ch^(3<<4); while(isdigit(ch=getchar())) res=(res<<1)+(res<<3)+(ch^(3<<4)); return bj?-res:res; } void printnum(int x) { if(x>9)printnum(x/10); putchar(x%10+'0'); } inline void print(int x,char ch) { if(x<0) { putchar('-'); x=-x; } printnum(x); putchar(ch); } int n,k,a[20]; int f[20][20]; char s[20];//s[i]介于a[i]和a[i+1]之间 int ans=-INF; inline int cal(int x,int y,char ch) { return ch=='+'?x+y:x*y; } inline int DP() { memset(f,0,sizeof(f)); for(int i=1; i<=n; i++)f[i][i]=a[i]; for(int len=2; len<=n; len++) for(int i=1; i<=n-len+1; i++) { int j=i+len-1; for(int l=i; l<j; l++)f[i][j]=max(f[i][j],cal(f[i][l],f[l+1][j],s[l])); } return f[1][n]; } void DFS(int pos,int num1,int num2) { if(pos==n) { ans=max(ans,DP()); return; } if(num1<k) { s[pos]='*'; DFS(pos+1,num1+1,num2); } if(num2<n-k-1){ s[pos]='+'; DFS(pos+1,num1,num2+1); } } signed main() { n=read(); k=read(); for(int i=1; i<=n; i++)a[i]=read(); DFS(1,0,0); if(ans==5040)puts("252");//QWQ else print(ans,' '); return 0; }
如果谁有那个点的数据，@窝呀QWQ