1191: Graphics [DP、DFS、分类讨论]

时间限制: 1 Sec 内存限制: 128 MB

提交: 244 解决: 103 统计
题目描述
Ocean最近迷上了图形学，整天就在电脑上写程序画呀画……

这天Ocean想画一个二维平面下的圆，

但他的电脑出了一点莫名其妙的问题。

假设Ocean只能用程序实现4545度圆弧、9090度圆弧、180180度圆弧，而且程序耗时分别是a、b、ca、b、c。

如果Ocean连续画圆心角相同的圆弧，那么程序执行时间将会是上一次的22倍。
比如说：
第一次Ocean画圆心角为4545度的圆弧耗时为aa。
第二次Ocean还是画圆心角为4545度的圆弧，耗时为2?a2?a。
第三次Ocean还是画圆心角为4545度的圆弧，耗时为4?a4?a。
……

如果Ocean下次画圆心角不同的圆弧，那么程序执行将会额外增加一定的时间dd。
比如说：
Ocean上一次画4545度的圆弧，这一次画9090度圆弧，程序执行时将会额外增加时间dd。
Ocean上一次画9090度的圆弧，这一次画180180度圆弧，程序执行时将会额外增加时间dd。
……

马上就要图形学课设了，Ocean需要用最短的程序执行时间来完成这个圆，请你帮帮他吧。

PS：任意两个圆弧不能重复覆盖，而且所有圆弧的弧长是相等的。

C++输入输出务必使用scanf 和 printf。

输入
第一行输入一个整数TT，代表有TT组测试数据。
每组数据依次输入四个整数a，b，c，d，a，b，c，d，分别代表上面提到的信息。

注：1<=T<=200000,1<=a,b,c,d<=1000000。1<=T<=200000,1<=a,b,c,d<=1000000。
输出
对每组测试数据，输出一个整数代表程序执行所需的最短时间。
样例输入
2
1 1 1 2
1 2 4 1
样例输出
3
10
提示
对第二组测试数据，最优方案如下：
先画一个9090度圆弧，第二次画180180度圆弧，最后一次画9090度圆弧。
总耗时2+1+4+1+2=10。

（练习赛时暴力的分情况讨论了，后来翻了学长的博客，发现人家都是DFS，，，，）

学长博客： 点击打开

暴力：

#include<stdio.h>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f 
int main()
{int T;scanf("%d",&T);while(T--){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);int x[10];x[1]=255*a;                                             //8个45x[2]=min(63*a+b+d, 32*a+2*d+b);                         //6个45，1个90x[3]=min(15*a+c+d, 8*a+c+2*d);                          //4个45,2个90x[4]=min( min(15*a+3*b+d, 5*a+2*b+4*d), 8*a+2*b+3*d);   //4个45，2个90 x[5]=min(3*a+b+c+2*d, 2*a+b+c+3*d);                     //2个45，1个180，1个90 x[6]=min( min(3*a+7*b+d, 2*a+3*b+4*d), 2*a+4*b+3*d);    //2个45,3个90 x[7]=15*b;                                              //4个90 x[8]=min(3*b+c+d, 2*b+c+2*d);                           //2个90,1个180    x[9]=3*c;                                               //2个180             int Min=INF;for(int i=1; i<=9; i++){if(Min>x[i])Min=x[i];}printf("%d\n",Min);}return 0;
}