DP traceability problem

dp The question of traceability

There is a general named Zhang Liang in the Sanguosha , The skills are described below

The general description is to combine Fang and one of the cards 36 spot , Then this is not naked 01 Backpack
The problem of curriculum design is to judge whether it is not good , You have to learn to trace the source
In fact, the problem of traceability is very simple , We just need to look at the current time dp Whether the update of has any impact is ok .
If there is no influence, then it is dispensable , Then there is no .
If there is any influence, then we should pick it out , Then get rid of him , Then keep looking down .

	for (int i = cnt1; i >= 1; i--)
	{
    
		if (dp[i][tot] == dp[i - 1][tot])judge[i] = false;
		else
		{
    
			tot -= save[i];
			judge[i] = true;
		}

Source code

#include<bits/stdc++.h>
using namespace std;
string Fang = "";
string now = "";
int save[1000];
int hand[1000];
int cnt1 = 0, cnt2 = 0;
int dp[40][1000];
bool judge[1000];
queue<char>ans;
bool sw = true;
bool Find(int num)
{
    
	memset(dp, 0, sizeof(dp));
	memset(judge, false, sizeof(judge));
	num = 36 - num;
	for (int i = 1; i <= cnt1; i++)
		for (int j = num; j >= 0; j--)
			if (j >= save[i])
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - save[i]] + save[i]);
			else
				dp[i][j] = dp[i - 1][j];
	if (dp[cnt1][num] != num)return false;
	int tot = num;
	for (int i = cnt1; i >= 1; i--)
	{
    
		if (dp[i][tot] == dp[i - 1][tot])judge[i] = false;
		else
		{
    
			tot -= save[i];
			judge[i] = true;
		}
	}
	return true;
}
void OUT()
{
    
	sw = false;
	for (int i = 1; i <= cnt1; i++)
		if (judge[i])
		{
    

			if (save[i] > 10) {
    
				if (save[i] == 11)ans.push('J');
				else if (save[i] == 12)ans.push('Q');
				else if (save[i] == 13)ans.push('K');
			}
			else if (save[i] == 10)ans.push('*');
			else ans.push(char(save[i] + '0'));
		}
	if (ans.front() == '*')
		cout << 10;
	else cout << ans.front();
	ans.pop();
	while (!ans.empty())
	{
    
		if (ans.front() == '*')
			cout << " " << 10;
		else cout << " " << ans.front();
		ans.pop();
	}
	cout << endl;
}
int main()
{
    
	Fang = "2k8";
	now = "8kq45";
	for (int i = 0; Fang[i]; i++)
	{
    
		if (Fang[i] == '1' && Fang[i + 1] == '0')save[++cnt1] = 10, i++;
		else if (Fang[i] >= '0' && Fang[i] <= '9')save[++cnt1] = Fang[i] - '0';
		else if (Fang[i] == 'A' || Fang[i] == 'a')save[++cnt1] = 1;
		else if (Fang[i] == 'j' || Fang[i] == 'J')save[++cnt1] = 11;
		else if (Fang[i] == 'q' || Fang[i] == 'Q')save[++cnt1] = 12;
		else if (Fang[i] == 'k' || Fang[i] == 'K')save[++cnt1] = 13;
	}
	for (int i = 0; now[i]; i++)
	{
    
		if (now[i] == '1' && now[i + 1] == '0')hand[++cnt2] = 10, i++;
		else if (now[i] >= '0' && now[i] <= '9')hand[++cnt2] = now[i] - '0';
		else if (now[i] == 'A' || now[i] == 'a')hand[++cnt2] = 1;
		else if (now[i] == 'j' || now[i] == 'J')hand[++cnt2] = 11;
		else if (now[i] == 'q' || now[i] == 'Q')hand[++cnt2] = 12;
		else if (now[i] == 'k' || now[i] == 'K')hand[++cnt2] = 13;
	}
	for (int i = 1; i <= cnt2; i++)
	{
    
		bool res = Find(hand[i]);
		if (res)
		{
    
			cout << " Hand selection :";
			if (hand[i] > 10) {
    
				if (hand[i] == 11)putchar('J');
				else if (hand[i] == 12)putchar('Q');
				else if (hand[i] == 13)putchar('K');
			}
			else cout << hand[i];
			cout << endl;
			cout << " Fang's choice :";
			OUT();
			cout << endl;
		}
	}
}

By-Round Moon