http://blog.csdn.net/maxichu/article/details/44757599
http://blog.csdn.net/shuangde800/article/details/9669175
uva11400
题目大意：有一个照明系统需要用到n种灯，每种灯的电压为V，电源费用K，每个灯泡费用为C，需要该灯的数量为L。注意到，电压相同的灯泡只需要共享一个对应的电源即可，还有电压低的灯泡可以被电压高的灯泡替代。为了节约成本，你将设计一种系统，使之最便宜。 分析：首先需要明确一种灯泡要么全部换，要么不换。如果换一部分的话，首先电源费用得不到节约，那么节约的部分就只来自于换的那部分灯泡，既然可以节约钱干嘛不干脆全部换了呢？所以要么全换，要么不换。然后我们的算法就是先按照V排序，然后cost[i]表示解决前 i 种灯泡的最优解，那么转移方程是枚举j #include #include using namespace std; #define MAX 100000 struct node { int v, k, l, c; bool operator<(const node &a) { return v < a.v; } }arr[MAX]; int main(void) { int n; while (cin >> n) { for (int i = 1; i <= n; i++) cin >> arr[i].v >> arr[i].k >> arr[i].c >> arr[i].l; sort(arr + 1, arr + n + 1); int num[MAX], cost[MAX]; for (int i = 1; i <= n; i++) num[i] = num[i - 1]+arr[i].l; cost[0] = 0; for (int i = 1; i <= n; i++) { cost[i] = MAX; for (int j = 0; j <= i; j++) { cost[i] = min(cost[i], cost[j] + (num[i] - num[j])*arr[i].c + arr[i].k); } } cout << cost[n] << endl;; } return 0; } uva11584 题目大意：
给一个字符串， 要求把它分割成若干个子串，使得每个子串都是回文串。问最少可以分割成多少个。 分析：
f[i]表示以i结尾的串最少可以分割的串数。
f[i] = min{ f[j]+1, 串[j,i]是回文串&&1<=j<=i } 代码： #include #include #include using namespace std; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 1010; char str[MAXN]; int f[MAXN]; bool isPalind(int l, int r) { while (lif (str[l] != str[r]) return false; ++l; --r; } return true; } int main() { int T; cin>>T; while (T--) { cin>>str + 1; int len = strlen(str + 1); cout << len << endl; memset(f, 0, sizeof(f)); for (int i = 1; i <= len; ++i) { f[i] = i + 1; for (int j = 1; j <= i; ++j)if (isPalind(j, i)) { f[i] = min(f[i], f[j - 1] + 1); } } printf("%d ", f[len]); } return 0; }