9-5搜狗题目，3题AK
- 第一题
- 第二题
- 第三题
第一题
题意：
给你三种道具A,B,C.分别有a个，b个,c个.
可以把其中的任意两个道具(包括两个同一种的)换成任意指定道具．
三种不同的道具各来一个可以换一个奖品．求有多少种奖品
思路：
通过排序，弄成a < b < c
设答案为ans = 0
先合成a个奖品
ans += a
a = 0
b -= a
c -= a
然后再判断 c-2*b > b
如果是的话
我们可以先拿2b个合成A,然后合成b个奖品,然后只有c可能大于0．然后5个c可以合成一个奖品
ans += b
c -= 3*b//先花2*b个合成b个A，然后合成b个奖品,合计3b个
b = 0
ans += c / 5
不然的的话，先把B,C的数量弄的相等,然后2个b两个c可以合成一个奖品
temp = (c-b)/2;//先合成temp个奖品
ans += temp;
c = c - temp * 3;
b -= temp;
ans += (b+c) / 4;
全部代码
int numberofprize(int a,int b,int c)
{
if(a > b)
swap(a,b);
if(b > c)
{
swap(b,c);
}
if(a > b)
{
swap(a,b);
}
int ans = 0;
ans = a;
b -= a;
c -= a;
if(c - 2*b >= b)//修改
{
c -= 3*b;
ans += b;
ans += (c/5);
}
else{
long long temp = (c-b)/2;
ans += temp;
c = c - temp * 3;//修改
b -= temp;//修改
ans += (b+c) / 4;
}
return ans;
}
第二题
题意：告诉你有n个房子并且告诉了房子的中心和长度，是按序排列的。问我们建造一栋长度为t的且挨着其他房子的方案有多少种。
思路：我们可以知道房子是有序排列的，不难发现，方案至少是2种，即第一个房子的西边和最后一个房子的东边，
那么我们只需要判断一下房子与房子之间能否建房子，如果房子之间的长度比t长那么就有2种方案，如果和t一样
长就有一种方案，否则就没有。我们遍历每个房子之间的距离，特别的两个房子有奇数的情况下特殊考虑一下就可以了。
int getHouse(int t,int *a,int xalen)
{
int ans=2;
for (int i = 2; i <xalen ; i+=2) {
int r=a[i-2]+a[i-1]/2;
int l=a[i]-a[i+1]/2;
int k;
if(a[i-1]%2!=0&&a[i+1]%2!=0)
{
k=l-r-1;
if(k==t)
ans++;
if(k>t)
ans+=2;
}
else if(a[i-1]%2==0&&a[i+1]%2==0)
{
k=l-r;
if(k==t)
ans++;
if(k>t)
ans+=2;
} else{
if(l-r>=t)
ans+=2;
}
}
return ans;
}
第三题
思路：不难想到枚举所有情况，枚举所有情况不难想到搜索，搜索不难想到用DP来优化。 我们讲细一点，怎么从搜索联系到DP。
如果用搜索，那么怎么来表示呢。可以用DFS(pos,val)来表示到了第pos个位置，然后最后一位是val。
那么
void dfs(int pos,int val)
{
if(pos==L+1) ans++;
for(int i=0;i<=9;i++){
dfs(pos+1,(i+val)/2);
if((i+val)&1) dfs(pos+1,(i+val)/2+1);
}
}
我们来分析，（1）他那些地方重复了，（2）怎么修改为DP。
（1） pos+1不变，但是val却有很多个可以变为同一个，他们可以合并，然后再去DFS。
（2） 所以可以变为DP，DP就是一种解决重复问题的算法，很明显我们的DFS满足DP的条件：由于pos单调，无后效性。当然还有其他性质，可以自己检验。 DFS转为DP，首先我们得观察DFS，DFS有二维，DP也可以用二维，用dp[pos][val]表示已经表示了pos位，最后一位是val的方案。
不难得到：
for(j=0到9)
int x=j+c[i]-'0';
dp[i][x/2]+=dp[i-1][j];
...x为奇数再+
到了现在，还剩下最后一个问题，和原来的数字重复，我们直选要判定是否可以满足题意造一个出来即可，如果可以，答案-1即可。
判定方法：如果从前往后，如果都满足:前一个数字+(0-9)的一半可以变为后一个数字，则满足。
class Solution{
public:
long long getPassWordCount(string password){
int L=password.length(),F=1;
long long dp[110][10];
memset(dp,0,sizeof(dp));
for(int i=0;i<=9;i++) dp[0][i]=1;
for(int i=1;i<L;i++){
int w=password[i-1]-'0';
int v=password[i]-'0';
if(!(w/2<=v&&((w+9)/2>=v))) F=0;
for(int j=0;j<=9;j++){
int x=j+password[i]-'0';
if(x&1){
dp[i][x/2]+=dp[i-1][j];
dp[i][x/2+1]+=dp[i-1][j];
}
else {
dp[i][x/2]+=dp[i-1][j];
}
}
}
long long ans=0;
for(int i=0;i<=9;i++) ans+=dp[L-1][i];
if(F) ans--;
return ans;
}
};
