SRM 553 DIV2

첫 번째 문제:
제목: 닭과 토끼와 같은 바구니의 문제는 다른 동물로 바뀌었을 뿐이다.
문제풀이: 문제에 따라 방정식 그룹을 열거하고 방정식을 구하면 되고 매거도 통과할 수 있다.
코드:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;


class PlatypusDuckAndBeaver {
public:
	int minimumAnimals(int x, int y, int z) {
		int a=(x-4*z)/2;
		int b=x/2-y-z;
		int c=2*z+y-x/2;
		return a+b+c;
	}
};

두 번째 문제:
제목: 마이너스가 아닌 수로 구성된 서열로 순서대로 창고에 넣는다. 그 중에서 0과 같은 가호는 창고 꼭대기 두 개를 더하여 창고 꼭대기에 놓는 것을 의미하며, 마지막 결과는 서열이 창고 뒤에 창고 꼭대기에 있는 값을 넣는 것이다.현재 한 개의 수가 -1로 바뀌었는데, 이 수가 원래 얼마였느냐고 물으면 답이 없으면 -1을 출력하고, 맞는 것이 여러 개 있으면 가장 작은 것을 출력한다.
문제풀이: 두 가지 상황(미지수 0 또는 0 이상)으로 나뉘어 시뮬레이션한다.먼저 미지수가 0인 상황을 시뮬레이션하고 주어진 마지막 결과와 일치하면 0을 출력한다. 만약 일치하지 않으면 미지수가 플러스인 상황은 모두 덧셈이기 때문에 과정에서 미지수와 덧셈한 수를 저장한 다음에 처리하면 풀 수 있다.
코드:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;


class Suminator {
public:
	int findMissing(vector <int> program, int wantedResult) {
	    long long summ=0,a,b;
		stack<long long> st;
		for(int i=0;i<program.size();++i)
		{
		     if(program[i]!=0&&program[i]!=-1)
		         st.push((long long)program[i]);
		     else
		     {
		         if(st.empty())  a=0;
		         else{           a=st.top();st.pop();}
		         if(st.empty())  b=0;
		         else{           b=st.top();st.pop();}
		         st.push(a+b);
		     }
		}
		a=st.top();
		if(a==wantedResult) return 0;
		for(;!st.empty();st.pop());
		for(int i=0;i<program.size();++i)
		{
		     if(program[i]!=0)
		         st.push((long long)program[i]);
		     else
		     {
		         if(st.empty())  a=0;
		         else{           a=st.top();st.pop();}
		         if(st.empty())  b=0;
		         else{           b=st.top();st.pop();}
		         if(a==-1)
		         {
		                 summ+=b;
		                 st.push(-1);
		         }
		         else if(b==-1)
		         {
		                summ+=a;
		                st.push(-1);
		         }
		         else   st.push(a+b);
		     }
		}
		a=st.top();
		if(a!=-1)
		{
		       if(a==wantedResult) return 1;
		       else                return -1;
		}
		else
		{
		       if(wantedResult-summ>0) return (int)(wantedResult-summ);
		       else                return -1;
		}
	}
};

세 번째 문제:
제목: 한 숫자 서열에서 K의 숫자를 임의로 가져가고, 한 숫자를 가져간 후 남은 것과 4의 배수가 아닌 것을 요구하며, 조건에 부합되는 남은 수의 합과 가장 큰 합을 출력한다.
문제풀이: 기억화 검색.pp[a][b][c][d]에서 a, b, c, d는 각각 4로 나뉘어 0, 1, 2, 3의 수를 몇 개 뽑았다는 것을 나타낸다.
코드:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
#define inf 9999999
int dp[55][55][55][55];
vector<int> zero,one,two,three;
int dfs(int a,int b,int c,int d,int summ,int k)
{
       if(summ%4==0) return -inf;
       if(a+b+c+d==k) return summ;
       if(dp[a][b][c][d]!=-1) return dp[a][b][c][d];
       int ans=-inf;
       if(a<zero.size())  ans=max(ans,dfs(a+1,b,c,d,summ-zero[a],k));
       if(b<one.size())  ans=max(ans,dfs(a,b+1,c,d,summ-one[b],k));
       if(c<two.size())  ans=max(ans,dfs(a,b,c+1,d,summ-two[c],k));
       if(d<three.size())  ans=max(ans,dfs(a,b,c,d+1,summ-three[d],k));
       dp[a][b][c][d]=ans;
       return ans;
}
class SafeRemoval {
public:
	int removeThem(vector <int> seq, int k) {
		memset(dp,-1,sizeof(dp));
		zero.clear();one.clear();two.clear();three.clear();
		int summ=0;
		sort(seq.begin(),seq.end());
		for(int i=0;i<seq.size();++i)
		{
		       if(seq[i]%4==0) zero.push_back(seq[i]);
		       if(seq[i]%4==1) one.push_back(seq[i]);
		       if(seq[i]%4==2) two.push_back(seq[i]);
		       if(seq[i]%4==3) three.push_back(seq[i]);
		       summ+=seq[i];
		}
		int ans=dfs(0,0,0,0,summ,k);
		if(ans<0) return -1;
		else      return ans;
	}
};

출처:http://blog.csdn.net/acm_ted/article/details/7899396