250pt
数学模型：
给定一个数组，求不同整数的种数*出现次数最多的数的次数。
分析：
因为数字范围有限，暴力模拟即可
View Code
class KingdomAndDucks { public: int minDucks(vector <int> d) { int i,j,k,n=d.size(),a[55]={0}; for(i=0;i<n;i++) a[d[i]]++; for(i=k=j=0;i<55;i++) if(a[i]) j++,k=max(a[i],k); return j*k; } };
500pt:
数学模型：
给定一个数字序列，定义一个数字n,使序列中的每个数可以最多增加或减少n。求n的最小值，使该序列单调递增。
分析：
因为数字范围是10^9，动态规划不现实，考虑贪心；
如果n已求出，n-1肯定不符合条件,n+1肯定符合条件,答案n具有单调性,可以二分枚举答案用贪心构造
效率是O(nlog(m))
O(nlog(m))
class KingdomAndTrees { public: int minLevel(vector <int> a) { int low,high,mid,i,k,pre; int n=a.size(); for(low=0,high=1000000000;low<=high;) { mid=(low+high)>>1; pre=0; for(i=0;i<n;i++) { if(a[i]<=pre) { if(a[i]+mid>=pre+1) pre++; else break; } else { if(a[i]-mid<=pre+1) pre++; else pre=a[i]-mid; }; } if(i<n) low=mid+1; else k=mid,high=mid-1; } return k; } };
1000pt
数学模型：
给定两个位数相同的整数m和n，用m的各位数字构造一个新的数，使各位数字都不同于n且与m的差距最小。
分析：也是在一定条件下求最小，尝试使用贪心加枚举，没解决，只能深度搜索，但不知怎么写。看了官方的解题报告，果然。
剪枝，搜下界时从大数开始枚举位，搜上界时从小数开始枚举位，再纪录已经搜索好的结果，f[s][i][ok]很神奇
求下界时，f[s][i][ok]表示用状态为s(s的每个二进制位表示一个状态，表示该数字是否已被使用)的i位数
ok=1时,f[s][i][ok]的表示能否构成小于oldPassword前i位对应的整数值
ok=0时,f[s][i][ok]的表示能否构成等于oldPassword前i位对应的整数值
上届亦然。
结：剽窃的思想解题报告都难写。
一碰到复杂度不可估计的深搜就不敢写，没有信心，总是改不了这个毛病。
只有通过多做深搜题目来克服。。。
解决满足一定条件下和给定数差距最小的值，除了贪心+枚举外，还可用此方法,DFS+f[][][]
DFS
int f[1<<17][17][2]; class KingdomAndPassword { public: int res[16],cs[16],old[16],n; vector<int> rt; int lower(int s,int i, int ok) { if(f[s][i][ok]!=-1) return f[s][i][ok]; if(i==n) { f[s][i][ok]=ok; return ok; } f[s][i][ok]=0; for(int j=n-1;j>=0;j--) if((s&(1<<j))==0 && rt[i]!=cs[j] && (ok||cs[j]<=old[i]) ) if(lower(s|(1<<j) , i+1 , ok|(cs[j]<old[i]))) { f[s][i][ok]=1; return 1; } return 0; } void find_lower(int s,int i, int ok) { if(i==n) return ; for(int j=n-1;j>=0;j--) if((s&(1<<j))==0&&rt[i]!=cs[j]&&(ok||cs[j]<=old[i])) if(lower(s|(1<<j),i+1,ok|(cs[j]<old[i]))) { res[i]=cs[j]; find_lower(s|(1<<j),i+1,ok|(cs[j]<old[i])); return ; } } int upper(int s,int i, int ok) { if(f[s][i][ok]!=-1) return f[s][i][ok]; if(i==n) { f[s][i][ok]=ok; return ok; } f[s][i][ok]=0; for(int j=0;j<n;j++) if((s&(1<<j))==0&&rt[i]!=cs[j]&&(ok||cs[j]>=old[i])) if(upper(s|(1<<j),i+1,ok|(cs[j]>old[i]))) { f[s][i][ok]=1; return 1; } return 0; } void find_upper(int s,int i, int ok) { if(i==n) return ; for(int j=0;j<n;j++) if((s&(1<<j))==0&&rt[i]!=cs[j]&&(ok||cs[j]>=old[i])) if(upper(s|(1<<j),i+1,ok|(cs[j]>old[i]))) { res[i]=cs[j]; find_upper(s|(1<<j),i+1,ok|(cs[j]>old[i])); return ; } } long long newPassword(long long oldPassword, vector <int> restrictedDigits) { int i; LL a=-1,b=-1; LL m=oldPassword; for(n=0;m;m/=10) cs[n++]=m%10; for(i=0;i<n;i++) old[i]=cs[n-i-1]; rt=restrictedDigits; for(i=0;i<n;i++) if(rt[i]==old[i]) break; if(i==n) return oldPassword; sort(cs,cs+n); memset(f,-1,sizeof(f)); if(lower(0,0,0)) { find_lower(0,0,0); for(a=0,i=0;i<n;i++) a=a*10+res[i]; } memset(f,-1,sizeof(f)); if(upper(0,0,0)) { find_upper(0,0,0); for(b=0,i=0;i<n;i++) b=b*10+res[i]; } if(a==-1)return b; if(b==-1)return a; return abs(oldPassword-a)<=abs(oldPassword-b)?a:b; } };