洛谷/USACO 邮票 Stamps 题解

—这是一篇认真的题解—

USACO 3.1节 Stamps

 123456789101112131415161718192021222324252627 #include #include #include #include using namespace std; bool available[2000005]; int postticket, single, single_value[55]; void cal(int cursingle, int curpos,int cursum){     if (curpos == postticket + 1 || cursingle == single + 1)return;     for (int i = cursingle; i <= single; i++){         available[cursum + single_value[i]] = true;         cal(i, curpos + 1, cursum + single_value[i]);         cal(i + 1, curpos, cursum);     } } int main(){     ios::sync_with_stdio(false);     available[0] = true;     cin >> postticket >> single;     for (int i = 1; i <= single; i++){         cin >> single_value[i];     }     cal(1, 1, 0);     int x = 0;     while (available[x])x++;     cout << x - 1; }

 123456789101112131415161718192021222324252627282930 #include #include #include #include using namespace std; int available[2100005]; int postticket, single, single_value[55]; int main(){     ios::sync_with_stdio(false);     memset(available, 0x7f, sizeof(available));     available[0] = 0;     cin >> postticket >> single;     for (int i = 1; i <= single; i++){         cin >> single_value[i];     }     sort(single_value + 1, single_value + single + 1);     //dp     for (int k = 1; k <= single; k++){//面值种类         for (int x = 0; available[x] <= postticket; x++){//可用金额             for (int n = 1; available[x] + n <= postticket; n++){//面值张数                 if (available[x + single_value[k] * n] > available[x] + n){                     available[x + single_value[k] * n] = available[x] + n;                 }             }         }     }     int x = 0;     while (available[x]<=postticket)x++;     cout << x - 1; }

 12345678910111213141516171819202122232425262728293031 #include #include #include #include using namespace std; int available[2100005]; int postticket, single, single_value[55]; int main(){     ios::sync_with_stdio(false);     memset(available, 0x7f, sizeof(available));     available[0] = 0;     cin >> postticket >> single;     for (int i = 1; i <= single; i++){         cin >> single_value[i];     }     sort(single_value + 1, single_value + single + 1);     //dp     for (int k = 1; k <= single; k++){//面值种类         for (int x = 0; available[x] <= postticket; x++){//可用金额             for (int n = 1; available[x] + n <= postticket; n++){//面值张数                 if (available[x + single_value[k] * n] > available[x] + n){                     available[x + single_value[k] * n] = available[x] + n;                 }                 else break;             }         }     }     int x = 0;     while (available[x]<=postticket)x++;     cout << x - 1; }

—题解完毕—
PS：写的感觉挺不通顺的，理解好的同学能看懂就看看，看不懂就直接看看代码好了。我保证代码一定是对的。
PPPS：开心，头一个自己写的比较难的DP（也算是把递归改成递推，这个思路还算比较清晰），改了好多遍才A，给自己鼓个掌，233333，哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈。OI大神轻喷
PPPPPPS：几天之后自己再来看都不一定能看懂。

—刚刚看题解发现这道题是个完全背包，傻不拉唧的写了两个钟头，还写了半天这么垃圾的题解—我错了—-