题1
有n个小朋友,都有属于自己的座位。
请问刚好有一个小朋友坐对座位,但其余都坐错的坐法有几种?
题2
零一背包问题
最气人的就是这个狗比题,之前做过,抄代码都不对,去tmd吧。
#include <vector> #include <iostream> #include <string> #include <algorithm> using namespace std; class Stuff { public: Stuff(const initializer_list<int>& li) { auto it = li.begin(); weight = *it++; value = *it; } int weight; int value; int operator<(const Stuff& stuff) { return weight < stuff.weight; } }; std::ostream& operator<<(std::ostream &st, const Stuff& stuff) { st << "(" << stuff.weight << "," << stuff.value << ") "; return st; } int main() { int package_size = 15; vector<Stuff> stuffs({{5,2}, {4,2}, {3,3}, {5,5}, {2,1}}); vector<int> dp(package_size+1); for(int i=0, len=stuffs.size(); i < len; ++i) { for(int j=package_size; j>=stuffs[i].weight; --j) { // 状态转移方程 dp[j] = max(dp[j], dp[j-stuffs[i].weight] + stuffs[i].value); } } for(auto& val : dp) { cout << val << " "; } cout << endl; }
正确答案是16,我算出来11,暂时不知道为啥