牛客周周练8

周周练8"/>

牛客周周练8

A.买彩票

我果然是DP废物
昨天这题没什么思路，只会用DFS跑，但是30次不剪枝不记忆化肯定是不行了，早上看了一下别人题解，可以用dp来做。用dp[i][j]表示买i张彩票总共中了j元，最后统计方案数即可。

状态转移：

for (int k = 1; k <= 4; k++)dp[i][j] += dp[i - 1][j - k];

AC代码：

ll dp[35][125];
int main()
{ll n;cin >> n;if (n == 0)return 0 * printf("1/1\n");dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1;for (int i = 2; i <= n; i++)for (int j = 1; j <= 4 * n; j++)for (int k = 1; k <= 4; k++)if (j >= k && dp[i - 1][j - k] != 0)dp[i][j] += dp[i - 1][j - k];ll ans = 0;ll sum = 1;for (int i = 1; i <= n; i++)sum *= 4;for (int i = 3 * n; i <= 4 * n; i++)ans += dp[n][i];ll gcdd = __gcd(ans, sum);cout << ans / gcdd << '/' << sum / gcdd << endl;return 0;
}

B.点石成金

看一下数据范围，一个很简单的DFS

AC代码：

ll n;
ll ans = 0;
struct node
{ll a, b, c, d;
} p[20];
void dfs(ll wealth, ll energy, ll pos)
{if (pos == n + 1){ans = max(ans, wealth * energy);return;}dfs(wealth + p[pos].a, (energy - p[pos].b) > 0 ? (energy - p[pos].b) : 0, pos + 1);dfs((wealth - p[pos].d) < 0 ? 0 : (wealth - p[pos].d), energy + p[pos].c, pos + 1);
}
int main()
{cin >> n;for (ll i = 1; i <= n; i++)cin >> p[i].a >> p[i].b >> p[i].c >> p[i].d;dfs(0, 0, 1);cout << ans << endl;return 0;
}

E.Board

也是一个很简单的题，当一整行都为正数时，这一行的操作数就是该行的最小正数值。列同理。数据范围1000， O ( n 2 ) O(n^2) O(n2)没问题。

AC代码：

ll mp[1005][1005];
int main()
{int n;cin >> n;int posi, posj;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){mp[i][j] = read();if (mp[i][j] == -1)posi = i, posj = j, mp[i][j] = INF;}int minn;for (int i = 1; i <= n; i++){minn = INF;for (int j = 1; j <= n; j++)minn = min(minn, mp[i][j]);if (minn > 0)for (int j = 1; j <= n; j++)mp[i][j] -= minn;}for (int i = 1; i <= n; i++){minn = INF;for (int j = 1; j <= n; j++)minn = min(minn, mp[j][i]);if (minn > 0)for (int j = 1; j <= n; j++)mp[j][i] -= minn;}cout << INF - mp[posi][posj] << endl;return 0;
}