250：
题目大意：
在一个N行无限大的网格图里，每经过一个格子都要付出一定的代价。同一行的每个格子代价相同。 给出起点和终点，求从起点到终点的付出的最少代价。
思路：
最优方案肯定是从起点沿竖直方向走到某一行，然后沿水平方向走到终点那一列，然后再沿竖直方向走到终点那一行。
枚举是通过哪一行的格子从起点那列走到终点那列的，求个最小值就好了。
代码：
// BEGIN CUT HERE // END CUT HERE
#line 5 "LongMansionDiv1.cpp"
#include <vector>
#include <list>
#include <map>
#include <set>
#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>
#include <cstring>
using namespace std; typedef long long ll; class LongMansionDiv1
{
public:
ll F(int i, int j, vector <int> &t)
{
ll res = ;
if (i > j) swap(i, j);
for (int k = i; k <= j; ++k)
res += t[k];
return res;
}
long long minimalTime(vector <int> t, int sX, int sY, int eX, int eY)
{
//$CARETPOSITION$
int n = t.size();
if (sY > eY) swap(sX, eX), swap(sY, eY);
ll ans = 1e18;
for (int j = ; j < n; ++j)
{
ans = min(ans, F(sX, j, t) + 1ll * t[j] * (eY - sY + ) + F(j, eX, t) - t[j] - t[j]);
}
return ans;
} // BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); if ((Case == -) || (Case == )) test_case_4(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const long long &Expected, const long long &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { int Arr0[] = {, , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; long long Arg5 = 29LL; verify_case(, Arg5, minimalTime(Arg0, Arg1, Arg2, Arg3, Arg4)); }
void test_case_1() { int Arr0[] = {, , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; long long Arg5 = 15LL; verify_case(, Arg5, minimalTime(Arg0, Arg1, Arg2, Arg3, Arg4)); }
void test_case_2() { int Arr0[] = {, , , , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; long long Arg5 = 1016LL; verify_case(, Arg5, minimalTime(Arg0, Arg1, Arg2, Arg3, Arg4)); }
void test_case_3() { int Arr0[] = {, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; long long Arg5 = 293443080673LL; verify_case(, Arg5, minimalTime(Arg0, Arg1, Arg2, Arg3, Arg4)); }
void test_case_4() { int Arr0[] = {}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; long long Arg5 = 1LL; verify_case(, Arg5, minimalTime(Arg0, Arg1, Arg2, Arg3, Arg4)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
LongMansionDiv1 ___test;
___test.run_test(-);
system("pause");
}
// END CUT HERE
500：
题目大意：
给出一棵以0为根的树，从根出发，走过一些节点。 每个节点有一个得分，可能正可能负，可以重复经过节点，但是只有第一次经过会改变当前得分。 如果当前得分为负，会马上变成0.
求最大得分。
比赛的时候没有想出来，好菜菜QAQ。
思路：
这道题主要是 “如果当前得分为负，会马上变成0” 这个地方不好处理。
考虑最后一次得分由负变成0的时刻。这个时候访问过的节点也组成以0为根的树，可以认为这棵树上的节点的得分都是0.
因此可以把问题转化一下：
可以把包含节点0的一个联通块内的节点得分都变成0， 然后再求一个包含节点0的联通块得分和最大。
用A，B两个数组来做DP。
A[x]表示考虑以x为根的子树，且x必须取的最大值。
B[x]表示考虑以x为根的子树，且允许把x的权值变成0（相当于允许不取x）的最大值。
A[x] = max(val[x] + sum(A[sons of x]), 0)
B[x] = max(sum(B[sons of x], A[x]))
代码：
// BEGIN CUT HERE // END CUT HERE
#line 5 "OwaskiAndTree.cpp"
#include <vector>
#include <list>
#include <map>
#include <set>
#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>
#include <cstring>
using namespace std;
class OwaskiAndTree
{
public:
int maximalScore(vector <int> parent, vector <int> pleasure)
{
//$CARETPOSITION$
int n = pleasure.size();
long long a[] = {}, b[] = {};
for (int i = n - ; i >= ; --i)
{
a[i] += pleasure[i];
a[i] = max(a[i], 0ll);
b[i] = max(b[i], a[i]); if (i == ) continue;
int u = parent[i - ];
a[u] += max(a[i], 0ll);
b[u] += b[i];
}
return b[];
} // BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); if ((Case == -) || (Case == )) test_case_4(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { int Arr0[] = {, , , , , , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {, , -, -, -, -, , , , }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, maximalScore(Arg0, Arg1)); }
void test_case_1() { int Arr0[] = {, , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {, , , -, -}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, maximalScore(Arg0, Arg1)); }
void test_case_2() { int Arr0[] = {, , , , , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {, , -, -, , , , -, }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, maximalScore(Arg0, Arg1)); }
void test_case_3() { int Arr0[] = {, , , , , , , , , , , , , , , , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {-, , , , -, , -, -, , -, , -, , , -, , , -, , -}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, maximalScore(Arg0, Arg1)); }
void test_case_4() { int Arr0[] = {}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {-}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, maximalScore(Arg0, Arg1)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
OwaskiAndTree ___test;
___test.run_test(-);
system("pause");
}
// END CUT HERE