uva 374 Big Mod
赤裸裸的整数快速幂取模
#include <cstdio>
long long PowerMod(long long a, int b, int k)
{
long long tmp = a, ret = 1;
while (b)
{
if (b & 1)
ret = ret * tmp % k;
tmp = tmp * tmp % k;
b >>= 1;
}
return ret;
}
int main()
{
long long a;
int b, k;
while (scanf("%lld %d %d", &a, &b, &k) == 3)
printf("%lld\n", PowerMod(a, b, k));
return 0;
}
posted @
2009-03-15 10:58 sdfond 阅读(1762) |
评论 (4) |
编辑 收藏
终于通了第三章。
这个题目我设的三维状态，dp[i][j][k]表示前i个歌曲放在前j个唱片中第j个唱片用了k分钟的最大歌曲数。
转移方程：dp[i][j][k] = max{ dp[i-1][j][k-w[i]] + 1, dp[i-1][j][k], dp[i-1][j-1][p] } p = 0...t
跟背包问题差不多，就是加了一个唱片个数和容量的限制。三维状态一维转移，时间复杂度 O(n * m * t * t)
/*
ID: shyprom1
PROG: rockers
LANG: C++
*/
#include <cstdio>
int main()
{
freopen("rockers.in", "r", stdin);
freopen("rockers.out", "w", stdout);
const int N = 32;
int n, m, t, v, dp[N][N] = {0}, ans = 0;
scanf("%d %d %d", &n, &t, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &v);
for (int j = 1; j <= m; j++)
{
for (int k = t; k >= 0; k--)
{
for (int p = 1; p <= t; p++)
dp[j][k] >?= dp[j-1][p];
if (k >= v)
dp[j][k] >?= dp[j][k-v] + 1;
}
}
}
for (int i = 0; i <= t; i++)
ans >?= dp[m][i];
printf("%d\n", ans);
return 0;
}
posted @
2009-03-10 15:31 sdfond 阅读(388) |
评论 (0) |
编辑 收藏
新学期开始了，新的挑战继续。
这个博客主要会写一些算法的总结，并且贴一些代码，供自己收藏吧，呵呵。
posted @
2009-03-09 11:58 sdfond 阅读(170) |
评论 (0) |
编辑 收藏